16

Are there any significant open problems in mathematics which are clearly decidable (in that it is easy to write a clearly corresponding program which will eventually output either Yes or No (or whatever sort of answer, out of finitely many possibilities, is appropriate), though it may take an implausibly long time to do so) but which remain open?

Dropping the qualifier "significant", examples of this sort of thing would be determining whether chess between perfect players results in a white win, black win, or stalemate; determining the $10^{10^{100}}$th decimal digit of $\pi$; etc. But none of these are of particular significance in mathematics, such that anyone would ordinarily list them as an open problem of note.

So, though it is inherently a subjective judgment: Are there any good examples of significant open problems of this sort?

(Edit: 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!)

Sridhar Ramesh
  • 5,642
  • 1
    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 '16 at 04:54
  • 6
    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. – Gerhard Paseman Dec 12 '16 at 04:55
  • 1
    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. – Robert Israel Dec 12 '16 at 05:17
  • @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. – Noam D. Elkies Dec 12 '16 at 05:18
  • 5
    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. – Noam D. Elkies Dec 12 '16 at 05:21
  • @Noam, I am not sure. The idoneal number problem could be semi-decidable. Gerhard "Is Not Even Half Sure" Paseman, 2016.12.11 – Gerhard Paseman Dec 12 '16 at 05:28
  • 2
    @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. – Noam D. Elkies Dec 12 '16 at 05:48
  • 5
    Is there a projective plane of order 12? – bof Dec 12 '16 at 09:16
  • 1
    @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. – Sridhar Ramesh Dec 12 '16 at 11:45
  • 1
    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. – Sridhar Ramesh Dec 12 '16 at 11:50
  • 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) – Sridhar Ramesh Dec 12 '16 at 11:51
  • @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)

     – Sridhar Ramesh Dec 12 '16 at 11:52
  • 3
    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! – Sridhar Ramesh Dec 12 '16 at 12:02
  • The following question is related, and is arguably a duplicate: http://mathoverflow.net/questions/74941/is-there-an-undecided-assertion-of-which-a-proof-that-its-not-undecidable-is/74956 – Timothy Chow Dec 12 '16 at 15:29
  • This question is also highly related: http://mathoverflow.net/questions/112097/important-open-problems-that-have-already-been-reduced-to-a-finite-but-infeasibl?noredirect=1&lq=1 – Sam Hopkins Dec 18 '16 at 18:03
  • 2
    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? – Joel David Hamkins Dec 18 '16 at 18:12
  • 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?". – Sridhar Ramesh Dec 19 '16 at 00:36
  • 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?" – Sridhar Ramesh Dec 19 '16 at 00:39
  • 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? – Joel David Hamkins Dec 19 '16 at 01:18
  • 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"…)

     – Sridhar Ramesh Dec 19 '16 at 07:42
  • 1
    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.]

     – Sridhar Ramesh Dec 19 '16 at 07:53
  • 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. – Sridhar Ramesh Dec 19 '16 at 08:00
  • 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. – Dirk Jun 02 '17 at 08:32

0 Answers0