Unsolved Problems due to Lack of Computational Power Er riuat D8l VwcH8: k: emSG
I was recently reading up about computational power and its uses in maths particularly to find counterexamples to conjectures. I was wondering are there any current mathematical problems which we are unable to solve due to our lack of computational power or inaccessibility to it.
What exactly am I looking for?
Problems of which we know that they can be solved with a finite (but very long) computation?
(e. g. NOT the Riemann hypothesis or twin prime conjecture)
I am looking for specific examples.
-
1$\\begingroup$ What exactly are you looking for? Problems of which we know that they can be solved with a finite (but very long) computation? (e. g. not the Riemann hypothesis or twin prime conjecture) $\\endgroup$ – 0x539 15 hours ago
-
$\\begingroup$ @stackupphysics I think you need to clarify whether "lack" refers to a technological insufficiency (e.g. we don't yet have enough processing power) or a theoretical insufficiency (e.g. even a perfect computer could never solve the problem). $\\endgroup$ – Jam 15 hours ago
-
$\\begingroup$ @0x539 I'll update $\\endgroup$ – StackUpPhysics 8 hours ago
-
1$\\begingroup$ Near duplicate on MO mathoverflow.net/q/112097/30186 $\\endgroup$ – Wojowu 2 hours ago
-
$\\begingroup$ Perhaps Skewes' number, the least $x$ for which $\\pi(x)\\le li(x)$. $\\endgroup$ – DanielWainfleet 44 mins ago
4 Answers
Goldbach's weak conjecture isn't a conjecture anymore, but before it was proved (in 2013), it had already been proved that it was true for every $n>e^{e^{16\\,038}}$. It was not computationally possible to test it for all numbers $n\\leqslant e^{e^{16\\,038}}$ though.
Some notorious problems of this kind are in discrete mathematics but involve a search space that is many magnitudes beyond what is feasible. For example the values of certain Ramsey numbers http://mathworld.wolfram.com/RamseyNumber.html or the existence of a Moore graph of degree 57 https://en.wikipedia.org/wiki/Moore_graph
-
$\\begingroup$ Ramsey numbers are the canonical “unfeasible computation”. As Erdős said, paraphrased by Joel H. Spencer: “Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens.” On the other hand [cont’d], $\\endgroup$ – Peter LeFanu Lumsdaine 2 hours ago
-
$\\begingroup$ [cont’d] …values of Ramsey numbers may not quite be what the OP is after, since they’re not typically considered as “counterexamples to a conjecture” (although of course they can be seen as such, in contrived ways). $\\endgroup$ – Peter LeFanu Lumsdaine 2 hours ago
Packing problems come to mind, i.e. how to achieve the densest packing of some kind of geometric objects, such as spheres or dodecahedrons. The interesting thing is that this is not a discrete problem, as there are uncountably many irregular, non-periodic packings that need to be checked. Still, the original proof of the sphere packing problem managed to turn this into a finite number of linear programming problems which then could be solved on a computer.
In theory you can use the same approach for objects other than spheres or in higher dimensions (and indeed people do), but in practice you reach a point quite soon, where there is simply not enough computing power to solve the resulting problems.
This is one of my own construction. I can construct a $3$-sided pyramid (with an open bottom) composed of $6$ dissimilar Pythagorean triples. The problem is finding a $3$-sided tile composed of $6$ other dissimilar Pythagorean triples that will close the bottom. I think such exists but I can't guess how much computer time it would take.
-
2$\\begingroup$ I don't think this fits the OP's criteria -- if no such tile exists, how are you going to prove it? Computing power alone is not enough here. $\\endgroup$ – TonyK 3 hours ago