Timeline for Are the Millennium Prize Problems all decidable?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 28, 2011 at 14:31 | vote | accept | Vijay Viswanathan | ||
| Apr 19, 2011 at 0:09 | comment | added | Henry Cohn | Another example is the existence and uniqueness of the monster simple group. It's obviously decidable (check all the possible multiplication tables), but not in any feasible way, and the actual proofs involve deep ideas. | |
| Apr 18, 2011 at 20:25 | comment | added | Timothy Chow | If you know that some particular mathematical claim is provable or disprovable in ZFC, then you can find the proof/disproof by exhaustive search. Therefore the only possible obstacle to actually finding the proof/disproof is computational infeasibility. Conversely, it is easy to cook up examples of decidable mathematical claims that are infeasible to decide. For instance, is the first decimal digit of Graham's number greater than 5? en.wikipedia.org/wiki/Graham%27s_number A more interesting example is whether there exists a projective plane of order 12. | |
| Apr 18, 2011 at 17:30 | comment | added | Thierry Zell | So the problem in $\mathbb{R}^5$ involves testing the emptiness of semi-algebraic set in 220 variables with 946 inequalities and 44 equations? Hmm... I can see why brute force will not help us here. :) | |
| Apr 18, 2011 at 17:29 | history | edited | David E Speyer | CC BY-SA 3.0 |
added 48 characters in body
|
| Apr 18, 2011 at 17:24 | comment | added | Harry Gindi | I was about to write a comment on the OP to this effect, but this answer is much more comprehensive, so +1. | |
| Apr 18, 2011 at 17:22 | history | answered | David E Speyer | CC BY-SA 3.0 |