16
$\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!)

Improve this question
$\endgroup$
23
  • 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
    Commented Dec 12, 2016 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
    Commented Dec 12, 2016 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
    Commented Dec 12, 2016 at 5:48
  • 5
    $\begingroup$ Is there a projective plane of order 12? $\endgroup$
    – bof
    Commented Dec 12, 2016 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
    Commented Dec 12, 2016 at 12:02

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .