Important open problems that have already been reduced to a finite but infeasible amount of computation - MathOverflow

Important open problems that have already been reduced to a finite but infeasible amount of computation

2012-11-11T18:19:59Z

Most open problems, when formalized, naturally involve quantification over infinite sets, thereby obviating the possibility, even in principle, of "just putting it on a computer."

Some questions (e.g. the existence of a projective plane of order 12) naturally resolve after a finite computation but not feasibly.

I'd like examples of reasonably important open problems that have now been reduced, via nontrivial arguments, to finite but infeasible computations.

I'm sure that additive number theory gives examples (certain questions along the lines of Goldbach conjecture and Waring's problem, but I don't have the details handy). I'd love especially to see examples that don't seem to originate in discrete mathematics.

Answer by Gerry Myerson for Important open problems that have already been reduced to a finite but infeasible amount of computation

2012-11-11T22:43:12Z

Baker's work on linear forms in logarithms reduced great big families of diophantine equations to finite searches. In many cases, sharpening of Baker's results plus large amounts of cleverness have brought the computations into the feasible range, but many other cases are still infeasible.

Answer by Tony Huynh for Important open problems that have already been reduced to a finite but infeasible amount of computation

2012-11-11T23:42:38Z

One of the most important open questions in graph theory is Hadwiger's conjecture, which asserts that every graph with no $K_{t}$-minor is $(t-1)$-colourable. The cases $t=1,2$ are trivially trivial, and the case $t=3$ is trivial. The case $t=4$ was actually proved by Hadwiger himself. The case $t=5$ was proved by Wagner to be equivalent to the Four colour theorem (and hence is true). The case $t=6$ was proved to hold by Robertson and Seymour and also uses the Four colour theorem. The case $t=7$ is open.

This naturally leads us to the question of given a fixed $t$, does Hadwiger's conjecture hold for $t$? Reed and Kawarabayashi proved that this question can be solved with a finite amount of computation. Namely, they prove:

There is a computable function $f(t)$ such that every counterexample to Hadwiger's conjecture for $t$, has at most $f(t)$ vertices.
For any fixed $t$, there is an $O(n^2)$-algorithm to decide if a graph with $n$ vertices is a counterexample to Hadwiger's conjecture for $t$.

Therefore, for any fixed $t$, Hadwiger's conjecture can be decided in finite time (but the amount of time is currently infeasible).

Answer by joro for Important open problems that have already been reduced to a finite but infeasible amount of computation

2012-11-12T06:31:49Z

Numerical evidence suggested $\pi(x)$ is always less than $\mathrm{li}(x)$.

Littlewood proved that $\pi(x) - \mathrm{li}(x)$ changes sign infinitely often, but the smallest $x$ s.t. $\pi(x) > \mathrm{li}(x)$ is currently not known. The smallest such $x$ is Skewes' number There is a crossing near $e^{727.95133}$. It is not known whether it is the smallest.

The problem possibly might be solved by some clever method other than naiively computing $\pi(x)$, but I don't see why this argument doesn't apply to the other answers.

Answer by Yoav Kallus for Important open problems that have already been reduced to a finite but infeasible amount of computation

2012-11-13T20:17:42Z

Voronoi gave an algorithm to enumerate all perfect quadratic forms in $n$ variables and consequently to identify the densest lattice packing of spheres in $\mathbb{R}^n$.

Answer by S. Sra for Important open problems that have already been reduced to a finite but infeasible amount of computation

2012-11-14T00:32:11Z

Computing Ramsey numbers or even tighter bounds on them is perhaps a prototypical example that fits the bill.

Answer by David White for Important open problems that have already been reduced to a finite but infeasible amount of computation

2012-11-14T03:29:28Z

Computing homotopy groups of spheres has been reduced in several different ways down to a finite but infeasible computation. This was discussed in another thread. John Klein's answer describes an algorithm Dan Kan came up with. The accepted answer points to other work which contains a more efficient method, but which I haven't read. I suppose you could argue that this is not an important enough problem (actually, this has also been done on MathOverflow), but most topologists would disagree. Certainly this is not a problem which originates in discrete math.

Answer by Joel David Hamkins for Important open problems that have already been reduced to a finite but infeasible amount of computation

2012-11-14T04:05:57Z

In principle, any mathematical question $\psi$ that is not independent of ZFC (or some standard stronger theory, such as ZFC+large cardinals) is reducible to the finite computational procedure: search for a proof of $\psi$ or a proof of $\neg\psi$. If the statement is not independent, then we will find one or the other; but such computation procedures are generally infeasible, with no known bound on their length. Meanwhile, if $\psi$ is provably independent of ZFC, then we may search for a proof of that. But alas, if our axioms are consistent, then some statements may be independent, but not provably so, and we can prove that if our axioms are consistent, then there will be such examples.

Meanwhile, there are many interesting and useful theories that have been proved to be decidable, but which have infeasible decision procedures. For example, any question of Cartesian geometry in any finite dimension is decidable in principle by computational means, since the theory of real-closed fields is decidable, meaning that in principle, we can decide the truth of any assertion expressible in the structure $\langle\mathbb{R},{+},{\cdot},{\lt},0,1\rangle$, which includes many interesting statements, many of which are natural open problems of the kind you seek, such as almost all the famous packing problems. Unfortunately, the best-known algorithms for this decision procedure are at least double-exponential time, and hence infeasible. Similarly, the theory of abelian groups is decidable; Presburger arithmetic is decidable; the theory of infinite chess is decidable and many other interesting theories, capable of expressing many natural problems.

So there would seem to be an abundance of examples of the type you seek.

Answer by Agol for Important open problems that have already been reduced to a finite but infeasible amount of computation

2012-11-14T04:43:44Z

Thurston asked for the maximal number of non-hyperbolic Dehn fillings on a one-cusped hyperbolic 3-manifold, and conjectured that the maximum is 10 which is only achieved by the figure eight knot complement. It's now been shown that the maximum is 10 by Lackenby-Meyerhoff, but I've also shown that there is an algorithm which will determine the finitely many manifolds with $>8$ exceptional Dehn fillings.

Answer by Andres Caicedo for Important open problems that have already been reduced to a finite but infeasible amount of computation

2012-11-14T06:38:47Z

This is an elaboration of a comment on Suvrit's answer.

Ramsey numbers can be defined for (infinite) ordinals, just as in the finite case: $r(\alpha,\beta)$ is the least $\gamma$ such that for any $2$-coloring of the edges of the complete graph on $\gamma$ vertices there is a set of vertices of type $\alpha$ whose induced graph is red, or a set of vertices of type $\beta$ whose induced graph is blue.

Ramsey's theorem gives that $r(\omega,\omega)=\omega$, but already $r(\omega+1,\omega)=\omega_1$. On the other hand, if $\alpha\lt\omega_1$ and $n$ is finite, then $r(\alpha,n)\lt\omega_1$, and for reasonably small infinite values of $\alpha$, one can attempt to compute $r(\alpha,n)$ explicitly. It turns out that this computation reduces to (Ramsey-theoretic) finite problems, which, just as with the classic computation of finite Ramsey numbers, quickly become unfeasible.

For example:

$r(\omega+3,3)=\omega\cdot2 + 8$. In general, if $0\lt n,m\lt\omega$, then $$ r(\omega+n,m)=\omega\cdot(m-1)+(g(n,m)-(m-1)), $$ where $g(n,m)$ is the least $k$ such that any $2$-coloring of the edges of the complete graph on set of vertices $\{1,\dots,k\}$ such that the induced graph on $C=\{1,\dots,m-1\}$ is blue, either admits a blue $K_m$, or a red $K_{n+1}$ with one of its vertices in $C$.

This was first established by Haddad and Sabbagh in 1969. One has $r(n+1,m)\le g(n,m)\lt\infty$, but typically the first inequality is strict. For example, $r(4,3)=9$ but $g(3,3)=10$. In general, computing $g(n,m)$ is similar to, but harder than computing $r(n+1,m)$.

$r(\omega\cdot3,3)=\omega\cdot9$. In general, if $0\lt n,m\lt\omega$, then $$ r(\omega\cdot n,m)=\omega\cdot l(n,m), $$ where $l(n,m)$ is the least $k$ such that any $2$-coloring of the edges of the complete digraph on $k$ vertices either contains a red complete digraph on $n$ vertices, or a blue transitive tournament on $m$ vertices.

Here, in complete digraphs we have two arrows (going in opposite directions) between any two distinct vertices. This was shown by Erdős and Rado in 1955. As with $g$, the computation of the values of $l(n,m)$ quickly becomes unfeasible.

$r(\omega^2\cdot2,3)=\omega^2\cdot10$. In general, if $0\lt n,m\lt\omega$, then $r(\omega^2\cdot m,n)=\omega^2\cdot h(m,n)$ for a Ramsey-theoretic function $h$ related to $3$-colorings of the edges of digraphs, though its exact description is somewhat technical to include here. This was shown fairly recently by Thilo Weinert, see here.

Answer by Jernej for Important open problems that have already been reduced to a finite but infeasible amount of computation

2012-11-14T06:40:01Z

I am not sure if this fits all the stated criterions but since it is a neat problem here it goes..

Is there a 57-regular graph $X$ of order 3250 , girth 5 and diameter 2?

$X$ is known as a Moore graph

A lot is known about $X$ (automorphism group has order less than 350), independence number is at most 400, the chromatic polynomial is $(x-57)(x+8)^{1520}(x-7)^{1729}$, but the search space of all potential graphs is still too large to be computed with an algorithm.

Answer by Nick Gill for Important open problems that have already been reduced to a finite but infeasible amount of computation

2012-11-14T09:06:22Z

You mention additive number theory in the question, so perhaps this isn't the type of example that you want. However my understanding is that the Three Primes Conjecture (every odd number $\geq 7$ is the sum of three primes) is now at the cusp of a feasible computer solution.

Vinogradov proved that the conjecture was true for all sufficiently large odd numbers (i.e. there exists $C>0$ such that every odd number greater than $C$ is the sum of three primes).

Various people have given explicit values for $C$ but, up until recently, the best (i.e. lowest) explicit value was $e^{3100}$. This is still, obviously, way out of computational range.

However Tao and, then, more recently Helfgott have improved these bounds by studying so-called `minor arcs', so that now one could just about imagine dealing with remaining cases via computer. The results of Helfgott are expressed in terms of a parameter $q$ pertaining to minor arcs. His work implies that the conjecture is true for $q>4\cdot 10^6$.

If you're interested you should read Helfgott's preprint which begins with a brief summary of the history of this problem.