Importantes problemas abiertos que ya se han reducido a una cantidad de cálculo finita pero inviable

Question

La mayoría de los problemas abiertos, cuando se formalizan, implican naturalmente la cuantificación sobre conjuntos infinitos, con lo que se obvia la posibilidad, incluso en principio, de "ponerlo en un ordenador".

Algunas cuestiones (por ejemplo, la existencia de un plano proyectivo de orden 12) se resuelven naturalmente tras un cálculo finito, pero no es factible.

Me gustaría tener ejemplos de problemas abiertos razonablemente importantes que ahora han sido reducido mediante argumentos no triviales, a cálculos finitos pero irrealizables.

Estoy seguro de que la teoría aditiva de los números da ejemplos (ciertas cuestiones en la línea de la conjetura de Goldbach y el problema de Waring, pero no tengo los detalles a mano). Me gustaría especialmente ver ejemplos que no parezcan originarse en la matemática discreta.

Answer 1

Informática grupos de homotopía de esferas se ha reducido de diferentes maneras hasta un cálculo finito pero inviable. Esto se discutió en otro hilo . La respuesta de John Klein describe un algoritmo ideado por Dan Kan. La respuesta aceptada apunta a otro trabajo que contiene un método más eficiente, pero que no he leído. Supongo que se podría argumentar que no es un problema lo suficientemente importante (en realidad, esto tiene también se ha hecho en MathOverflow), pero la mayoría de los topólogos no estarían de acuerdo. Ciertamente, este no es un problema que se origine en la matemática discreta.

Answer 2

Las pruebas numéricas sugieren $\pi(x)$ es siempre menor que $\mathrm{li}(x)$ .

Littlewood demostró que $\pi(x) - \mathrm{li}(x)$ cambia de signo infinitamente a menudo, pero el más pequeño $x$ s.t. $\pi(x) > \mathrm{li}(x)$ no se conoce actualmente. El más pequeño de estos $x$ es El número de Skewes Hay un cruce cerca de $e^{727.95133}$ . No se sabe si es el más pequeño.

El problema podría resolverse con algún método inteligente que no sea la computación ingenua $\pi(x)$ , pero no veo por qué este argumento no se aplica a las otras respuestas.

Answer 3

Una de las cuestiones abiertas más importantes en la teoría de grafos es La conjetura de Hadwiger que afirma que todo gráfico sin $K_{t}$ -menor es $(t-1)$ -colorables. Los casos $t=1,2$ son triviales, y el caso $t=3$ es trivial. El caso $t=4$ fue demostrado por el propio Hadwiger. El caso $t=5$ fue demostrada por Wagner como equivalente al teorema de los cuatro colores (y por lo tanto es verdadera). El caso $t=6$ fue demostrada por Robertson y Seymour y también utiliza el teorema de los cuatro colores. El caso $t=7$ está abierto.

Esto nos lleva naturalmente a la cuestión de que dado un $t$ ¿se cumple la conjetura de Hadwiger para $t$ ? Reed y Kawarabayashi demostraron que esta cuestión puede resolverse con una cantidad finita de cálculos. En concreto, demuestran:

1. Existe una función computable $f(t)$ tal que todo contraejemplo mínimo a la conjetura de Hadwiger para $t$ tiene como máximo $f(t)$ vértices.

2. Para cualquier $t$ Hay un $O(n^2)$ -para decidir si un gráfico con $n$ vértices es un contraejemplo a la conjetura de Hadwiger para $t$ .

Por lo tanto, para cualquier $t$ La conjetura de Hadwiger puede decidirse en un tiempo finito (pero la cantidad de tiempo es actualmente inviable).

Answer 4

El trabajo de Baker sobre las formas lineales en logaritmos redujo grandes familias de ecuaciones diofantinas a búsquedas finitas. En muchos casos, la agudización de los resultados de Baker más grandes cantidades de ingenio han llevado los cálculos al rango factible, pero muchos otros casos siguen siendo inviables.

Answer 5

En principio, cualquier cuestión matemática $\psi$ que no es independiente de ZFC (o de alguna teoría estándar más fuerte, como ZFC+grandes cardinales) es reducible al procedimiento computacional finito: buscar una prueba de $\psi$ o una prueba de $\neg\psi$ . Si el enunciado no es independiente, entonces encontraremos uno u otro; pero tales procedimientos de cálculo son generalmente inviables, sin que se conozca el límite de su longitud. Mientras tanto, si $\psi$ es demostrablemente independiente de ZFC, entonces podemos buscar una prueba de ello. Pero, por desgracia, si nuestros axiomas son consistentes, entonces algunos enunciados pueden ser independientes, pero no demostrables, y podemos demostrar que si nuestros axiomas son consistentes, entonces habrá tales ejemplos.

Mientras tanto, hay muchas teorías interesantes y útiles que se han demostrado decidibles, pero que tienen procedimientos de decisión inviables. Por ejemplo, cualquier cuestión de geometría cartesiana en cualquier dimensión finita es decidible en principio por medios computacionales, ya que la teoría de los campos reales cerrados es decidible lo que significa que, en principio, podemos decidir la verdad de cualquier afirmación expresable en la estructura $\langle\mathbb{R},{+},{\cdot},{\lt},0,1\rangle$ que incluye muchos enunciados interesantes, muchos de los cuales son problemas abiertos naturales del tipo que usted busca, como casi todos los famosos problemas de empaquetamiento. Desgraciadamente, los algoritmos más conocidos para este procedimiento de decisión son, como mínimo, de tiempo doblemente exponencial y, por tanto, inviables. Del mismo modo, la teoría de los grupos abelianos es decidible; Aritmética de Presburgo es decidible; el teoría del ajedrez infinito es decidible y muchas otras teorías interesantes, capaces de expresar muchos problemas naturales.

Así que parece que hay una abundancia de ejemplos del tipo que usted busca.