Timeline for Decidable open problems
Current License: CC BY-SA 3.0
32 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 17, 2017 at 20:19 | review | Close votes | |||
| Dec 18, 2017 at 1:19 | |||||
| Jun 2, 2017 at 8:32 | comment | added | Dirk | As you stated, every problem of the form "Is there a finite structure (from a finite set of such structures) with property P?" would match your criterion. There are many such problems still unsolved. If they are significant or not surely depends on who you ask. E.g. in coding theory, finding an optimal doubly even binary code of length 72 is still open and there are multiple papers on this problem. Here, you could simply compute all such codes in finite time and thus decide it with an algorithm. | |
| Jun 2, 2017 at 8:23 | history | edited | Sridhar Ramesh | CC BY-SA 3.0 |
Minor wording thing
|
| Dec 19, 2016 at 8:00 | comment | added | Sridhar Ramesh | And: yes. Any open question which is KNOWN not to be independent from a specified formal system all agree on as the appropriate arbiter of the matter counts as an example of the sort of thing I'm looking for. (Indeed, every example can be viewed as of this form; that was the point of my second comment 7 hours ago). That is exactly what I am looking for. | |
| Dec 19, 2016 at 7:53 | comment | added | Sridhar Ramesh | If you like, another phrasing: I am looking for examples of programs for which A) The program is known to halt with output either Yes or No, but… B) Which of those two outputs specifically occurs is not known, and in fact this is considered the answer to a significant open problem. [I found it more natural to speak in terms of problems than programs, but it amounts to the same thing.] | |
| Dec 19, 2016 at 7:42 | comment | added | Sridhar Ramesh | There is a difference between "There is a program P such that it is known that P outputs the answer to Q" and "It is known that there is a program P such that P outputs the answer to Q". The existential quantifier and the "It is known that…" modality do not commute. The former situation is what I am interested in. Examples of things considered significant open problems in math for which I could sit down and write a program, today, right now, that all agree would settle the matter if only run long enough. (Actually, better than the word "known" for my purposes may be "accepted" or "taken"…) | |
| Dec 19, 2016 at 1:18 | comment | added | Joel David Hamkins | Since the "always say Yes" and "always say No" algorithms provably halt, then any open question which is not independent will be subject to such a provable algorithm, since it will be provable that one or other algorithm gives the right answer. So your provisions don't actually restrict much. Because of this, you seem to be asking for instances of open questions that are independent of some axiomatic system, but you haven't at all specified which axiomatic system you have in mind. ZFC? ZFC + large cardinals, or what? Does the question make sense without explicitly addressing these issues? | |
| Dec 19, 2016 at 0:39 | comment | added | Sridhar Ramesh | An equivalent formulation is "Here is a formal system which is known to yield one and only one of the statements {X1, X2, ..., Xn} as a consequence. (Cleverness would not be necessary if we had all the time in the world. It's just a matter of enumerating through all the possible derivations). Which such statement results?" | |
| Dec 19, 2016 at 0:36 | comment | added | Sridhar Ramesh | That there is a known program which provably gives the correct answer; that the problem is manifestly, or by now known to be, equivalent to a specific one of the form "What does this (known to halt) program output?". | |
| Dec 18, 2016 at 18:12 | comment | added | Joel David Hamkins | A proper formalization of the question suffers from the fact that every individual question is decidable: the right answer is given either by the "say Yes" algorithm or by the "say No" algorithm, and both of these are computable. The concept of a decidable problem is only sensible when there is an input parameter. So what do you mean exactly? | |
| Dec 18, 2016 at 18:03 | comment | added | Sam Hopkins | This question is also highly related: mathoverflow.net/questions/112097/… | |
| Dec 18, 2016 at 17:53 | history | reopened |
Bjørn Kjos-Hanssen Timothy Chow Stefan Kohl♦ Jan-Christoph Schlage-Puchta Jeremy Rouse |
||
| Dec 18, 2016 at 3:07 | review | Reopen votes | |||
| Dec 18, 2016 at 17:53 | |||||
| Dec 12, 2016 at 15:29 | comment | added | Timothy Chow | The following question is related, and is arguably a duplicate: mathoverflow.net/questions/74941/… | |
| Dec 12, 2016 at 12:11 | review | Reopen votes | |||
| Dec 12, 2016 at 16:01 | |||||
| Dec 12, 2016 at 12:02 | comment | added | Sridhar Ramesh | Incidentally, I nominate this question for reopening as NOT a duplicate, in that the question it has been marked a duplicate of specifically excludes problems that "naturally resolve after a finite computation", being interested only in problems which nontrivially reduce to finite computation. My interest is in either, but for me, the ideal examples are those that are manifestly finite computations from the start! | |
| Dec 12, 2016 at 11:59 | history | edited | Sridhar Ramesh | CC BY-SA 3.0 |
added 443 characters in body
|
| Dec 12, 2016 at 11:52 | comment | added | Sridhar Ramesh | @bof: That's another good example, thanks; although in a sense it's just a specific case of the more general pressing question, "Are there projective planes of non-prime power order?", which is only semidecidable. (It'd be great if there were natural examples that were both important and not just special cases of more general semidecidable questions! But I thank everyone for their contributions so far) | |
| Dec 12, 2016 at 11:51 | comment | added | Sridhar Ramesh | Noam D Elkies: Thanks, that Moore graph example is a good one (even if, as you say, math would not be advanced much either way) | |
| Dec 12, 2016 at 11:50 | comment | added | Sridhar Ramesh | Gerhard Paseman and Robert Israel: Thanks, but I am not looking for semidecidable propositions; open problems of quantifier complexity 1 are very common. I am only looking for decidable propositions. | |
| Dec 12, 2016 at 11:45 | comment | added | Sridhar Ramesh | @james.nixon: The same is true of any problem with quantifier complexity 1; that is, problems of the form "Does there exist a finite structure F such that decidable property P holds of F?" are always false if undecidable, and their negations "Do all finite structures F satisfy decidable property Q?" are always true if undecidable. | |
| Dec 12, 2016 at 10:46 | history | closed |
Nate Eldredge Bjørn Kjos-Hanssen Wolfgang Douglas Zare Marco Golla |
Duplicate of Important open problems that have already been reduced to a finite but infeasible amount of computation | |
| Dec 12, 2016 at 9:16 | comment | added | bof | Is there a projective plane of order 12? | |
| Dec 12, 2016 at 5:55 | review | Close votes | |||
| Dec 12, 2016 at 10:46 | |||||
| Dec 12, 2016 at 5:48 | comment | added | Noam D. Elkies | @GerhardPaseman certainly if there's a 66th(?) idoneal number (in defiance of ERH etc.) then it's decidable, but the OP asked that it should be "clearly decidable" regardless of whether the answer is Yes or No. | |
| Dec 12, 2016 at 5:28 | comment | added | Gerhard Paseman | @Noam, I am not sure. The idoneal number problem could be semi-decidable. Gerhard "Is Not Even Half Sure" Paseman, 2016.12.11 | |
| Dec 12, 2016 at 5:21 | comment | added | Noam D. Elkies | There's the Moore graph(s) of degree $57$, though I doubt that mathematics would be advanced much if such a graph was either found or proved not to exist by exhaustive computation. | |
| Dec 12, 2016 at 5:18 | comment | added | Noam D. Elkies | @GerhardPaseman Are you sure about the idoneal number problem? Without the Riemann hypothesis for imaginary quadratic characters (or at least the nonexistence of a Siegel zero) I don't know how to prove that it is decidable if (as expected) there are no further examples. | |
| Dec 12, 2016 at 5:17 | comment | added | Robert Israel | It is conjectured that there are infinitely many Wall-Sun-Sun primes, but none are currently known. If the conjecture is true, a finite search will find one. According to Wikipedia, as of April 2016 the search had gone up to $1.9 \times 10^{17}$ without finding one. On the other hand, it's just a conjecture, so the search might not terminate. | |
| Dec 12, 2016 at 4:55 | comment | added | Gerhard Paseman | There are many in combinatorics. Estimating Ramsey numbers exactly is open for various sizes. Hadamard's maximum determinant problem is semi-decidable in that a no answer might occur after a finite computation. Many Diophantine equations of interest are proven to have finitely many solutions, but it is not known what they are. Idoneal numbers are another. You could likely compile a list from online sources such as the Open Problem Garden. Gerhard "Perhaps Ask A Narrower Question?" Paseman, 2016.12.11. | |
| Dec 12, 2016 at 4:54 | comment | added | user78249 | Kind of unrelated, but it seems like a good joke to add here. I have read that if one can show the Riemann-hypothesis is undecidable and it is false, we arrive at a contradiction because if it were false there would be a zero outside the strip determining it is decidable. But if the Riemann hypothesis is undecidable, we arrive at a kind of paradox--it can't be proven. However, since it can't be both undecidable and false, it necessarily follows that if the Riemann Hypothesis is undecidable, it is true... Just a little math joke about "open problems" and "decidability". | |
| Dec 12, 2016 at 4:45 | history | asked | Sridhar Ramesh | CC BY-SA 3.0 |