15
$\begingroup$

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!)

$\endgroup$
  • 6
    $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Dec 12 '16 at 4:55
  • 5
    $\begingroup$ 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. $\endgroup$ – Noam D. Elkies Dec 12 '16 at 5:21
  • 2
    $\begingroup$ @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. $\endgroup$ – Noam D. Elkies Dec 12 '16 at 5:48
  • 5
    $\begingroup$ Is there a projective plane of order 12? $\endgroup$ – bof Dec 12 '16 at 9:16
  • 3
    $\begingroup$ 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! $\endgroup$ – Sridhar Ramesh Dec 12 '16 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.