Important open problems that have already been reduced to a finite but infeasible amount of computation - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T23:39:31Z http://mathoverflow.net/feeds/question/112097 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/112097/important-open-problems-that-have-already-been-reduced-to-a-finite-but-infeasible Important open problems that have already been reduced to a finite but infeasible amount of computation David Feldman 2012-11-11T18:19:59Z 2012-11-14T09:06:22Z <p>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."</p> <p>Some questions (e.g. the existence of a projective plane of order 12) naturally resolve after a finite computation but not feasibly.</p> <p>I'd like examples of reasonably important open problems that have now been <em>reduced</em>, via nontrivial arguments, to finite but infeasible computations. </p> <p>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.</p> http://mathoverflow.net/questions/112097/important-open-problems-that-have-already-been-reduced-to-a-finite-but-infeasible/112123#112123 Answer by Gerry Myerson for Important open problems that have already been reduced to a finite but infeasible amount of computation Gerry Myerson 2012-11-11T22:43:12Z 2012-11-11T22:43:12Z <p>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. </p> http://mathoverflow.net/questions/112097/important-open-problems-that-have-already-been-reduced-to-a-finite-but-infeasible/112131#112131 Answer by Tony Huynh for Important open problems that have already been reduced to a finite but infeasible amount of computation Tony Huynh 2012-11-11T23:42:38Z 2012-11-12T01:04:52Z <p>One of the most important open questions in graph theory is <a href="http://en.wikipedia.org/wiki/Hadwiger_conjecture_%28graph_theory%29" rel="nofollow">Hadwiger's conjecture</a>, 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. </p> <p>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: </p> <ol> <li><p>There is a computable function $f(t)$ such that every counterexample to Hadwiger's conjecture for $t$, has at most $f(t)$ vertices. </p></li> <li><p>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$.</p></li> </ol> <p>Therefore, for any fixed $t$, Hadwiger's conjecture can be decided in finite time (but the amount of time is currently infeasible). </p> http://mathoverflow.net/questions/112097/important-open-problems-that-have-already-been-reduced-to-a-finite-but-infeasible/112149#112149 Answer by joro for Important open problems that have already been reduced to a finite but infeasible amount of computation joro 2012-11-12T06:31:49Z 2012-11-14T06:31:59Z <p>Numerical evidence suggested $\pi(x)$ is always less than $\mathrm{li}(x)$.</p> <p>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 <a href="http://en.wikipedia.org/wiki/Skewes%27_number" rel="nofollow">Skewes' number</a> There is a crossing near $e^{727.95133}$. It is not known whether it is the smallest.</p> <p>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.</p> http://mathoverflow.net/questions/112097/important-open-problems-that-have-already-been-reduced-to-a-finite-but-infeasible/112315#112315 Answer by Yoav Kallus for Important open problems that have already been reduced to a finite but infeasible amount of computation Yoav Kallus 2012-11-13T20:17:42Z 2012-11-13T20:17:42Z <p>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$.</p> http://mathoverflow.net/questions/112097/important-open-problems-that-have-already-been-reduced-to-a-finite-but-infeasible/112331#112331 Answer by S. Sra for Important open problems that have already been reduced to a finite but infeasible amount of computation S. Sra 2012-11-14T00:32:11Z 2012-11-14T00:32:11Z <p>Computing <a href="http://en.wikipedia.org/wiki/Ramsey%27s_theorem#Ramsey_numbers" rel="nofollow">Ramsey numbers</a> or even tighter bounds on them is perhaps a prototypical example that fits the bill.</p> http://mathoverflow.net/questions/112097/important-open-problems-that-have-already-been-reduced-to-a-finite-but-infeasible/112341#112341 Answer by David White for Important open problems that have already been reduced to a finite but infeasible amount of computation David White 2012-11-14T03:29:28Z 2012-11-14T03:29:28Z <p>Computing <strong>homotopy groups of spheres</strong> has been reduced in several different ways down to a finite but infeasible computation. This was discussed in <a href="http://mathoverflow.net/questions/31004/computational-complexity-of-computing-homotopy-groups-of-spheres" rel="nofollow">another thread</a>. 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 <a href="http://mathoverflow.net/questions/22837/what-are-the-uses-of-the-homotopy-groups-of-spheres" rel="nofollow">also been done</a> on MathOverflow), but most topologists would disagree. Certainly this is not a problem which originates in discrete math.</p> http://mathoverflow.net/questions/112097/important-open-problems-that-have-already-been-reduced-to-a-finite-but-infeasible/112342#112342 Answer by Joel David Hamkins for Important open problems that have already been reduced to a finite but infeasible amount of computation Joel David Hamkins 2012-11-14T04:05:57Z 2012-11-14T05:11:18Z <p>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. </p> <p>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 <a href="http://en.wikipedia.org/wiki/Real_closed_field#Model_theory%3a_decidability_and_quantifier_elimination" rel="nofollow">the theory of real-closed fields is decidable</a>, 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; <a href="http://en.wikipedia.org/wiki/Presburger_arithmetic" rel="nofollow">Presburger arithmetic</a> is decidable; the <a href="http://jdh.hamkins.org/the-mate-in-n-problem-of-infinite-chess-is-decidable/" rel="nofollow">theory of infinite chess</a> is decidable and many other interesting theories, capable of expressing many natural problems. </p> <p>So there would seem to be an abundance of examples of the type you seek.</p> http://mathoverflow.net/questions/112097/important-open-problems-that-have-already-been-reduced-to-a-finite-but-infeasible/112346#112346 Answer by Agol for Important open problems that have already been reduced to a finite but infeasible amount of computation Agol 2012-11-14T04:43:44Z 2012-11-14T04:43:44Z <p>Thurston asked for the maximal number of non-hyperbolic <a href="http://en.wikipedia.org/wiki/Dehn_filling" rel="nofollow">Dehn fillings</a> 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 <a href="http://front.math.ucdavis.edu/0808.1176" rel="nofollow">Lackenby-Meyerhoff</a>, but I've also shown that <a href="http://www.ams.org/mathscinet-getitem?mr=2680207" rel="nofollow">there is an algorithm which will determine the finitely many manifolds with $>8$ exceptional Dehn fillings</a>. </p> http://mathoverflow.net/questions/112097/important-open-problems-that-have-already-been-reduced-to-a-finite-but-infeasible/112353#112353 Answer by Andres Caicedo for Important open problems that have already been reduced to a finite but infeasible amount of computation Andres Caicedo 2012-11-14T06:38:47Z 2012-11-14T06:58:35Z <p>This is an elaboration of a comment on Suvrit's answer. </p> <p>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. </p> <p>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. </p> <p>For example:</p> <ul> <li>$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 <code>$\{1,\dots,k\}$</code> such that the induced graph on <code>$C=\{1,\dots,m-1\}$</code> is blue, either admits a blue $K_m$, or a red $K_{n+1}$ with one of its vertices in $C$.</li> </ul> <p>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)$. </p> <ul> <li>$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. </li> </ul> <p>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.</p> <ul> <li>$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 <a href="http://www.math.uni-bonn.de/people/weinert/Poetry.pdf" rel="nofollow">here</a>. </li> </ul> http://mathoverflow.net/questions/112097/important-open-problems-that-have-already-been-reduced-to-a-finite-but-infeasible/112354#112354 Answer by Jernej for Important open problems that have already been reduced to a finite but infeasible amount of computation Jernej 2012-11-14T06:40:01Z 2012-11-14T06:56:27Z <p>I am not sure if this fits all the stated criterions but since it is a neat problem here it goes..</p> <p>Is there a 57-regular graph $X$ of order 3250 , girth 5 and diameter 2?</p> <p>$X$ is known as a <a href="http://en.wikipedia.org/wiki/Moore_graph" rel="nofollow">Moore</a> graph</p> <p>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.</p> http://mathoverflow.net/questions/112097/important-open-problems-that-have-already-been-reduced-to-a-finite-but-infeasible/112369#112369 Answer by Nick Gill for Important open problems that have already been reduced to a finite but infeasible amount of computation Nick Gill 2012-11-14T09:06:22Z 2012-11-14T09:06:22Z <p>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 <strong>Three Primes Conjecture</strong> (every odd number $\geq 7$ is the sum of three primes) is now at the cusp of a feasible computer solution.</p> <p>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).</p> <p>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. </p> <p>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$.</p> <p>If you're interested you should read <a href="http://arxiv.org/abs/1205.5252" rel="nofollow">Helfgott's preprint</a> which begins with a brief summary of the history of this problem.</p>