¿Para qué problemas del milenio es indecidible -> verdadero?

Question

Se recibieron tres buenas respuestas -de Alex Gavrilov, Bjørn Kjos-Hanssen y Terry Tao- y la recompensa se ha concedido (de forma un tanto arbitraria) a Alex Gavrilov.

Las respuestas se resumen a continuación; como son abiertas y técnicamente sutiles, la pregunta se ha marcado para convertirla en Wiki comunitaria.

Se agradece a todos los que han contribuido.

---

Resumen   Harry Altman comentó de manera convincente :

En esencia, se trata de preguntar cuál de estas afirmaciones es equivalente a una $\Pi^0_1$ declaración, ¿verdad?

Incorporamos esta idea a una versión mejorada de la pregunta:

¿Cuál de los problemas del Premio del Milenio puede ser enunciado como un postulado que puede ser falsificado por un $\Pi^0_1$ ¿contraejemplo?

a lo que las respuestas dadas (según entiendo) equivalen:

1. "La hipótesis de Riemann es cierta" a $\Pi^0_1$ podría existir un contraejemplo ;
   (por Comentario de Noam Elkies )
2. "La conjetura de Birch y Swinnerton-Dyer es cierta" posiblemente un $\Pi^0_1$ Se podría construir un contraejemplo, pero no con los conocimientos actuales (por Respuesta de Alex Gavrilov );
3. " $\mathsf{P}\ne\mathsf{NP}$ " no es obvio $\Pi^0_1$ contraejemplo
   (por Respuesta de Bjørn Kjos-Hanssen );
4. "Navier-Stokes es globalmente regular" no es obvio $\Pi^0_1$ contraejemplo
   (por Respuesta de Terry Tao );
5. "Yang-Mills tiene una brecha de masa" no es obvio $\Pi^0_1$ contraejemplo (?) ;
6. "La conjetura de Hodge es cierta" no es obvio $\Pi^0_1$ contraejemplo (?) ;

Recursos   Artículo de Wikipedia Jerarquía aritmética explica la notación de la respuesta de Harry Altman.

Lo que "no es obvio $\Pi^0_1$ Contraejemplo" Significa    Como era anotado en el weblog de Dick Lipton y Ken Regan La carta perdida de Gödel y P=NP La autoridad de la Consejo Asesor Científico (SAB) del Clay Mathematics Institute (CMI) se extiende a:

"El CEC puede considerar la posibilidad de recomendar la concesión del premio a una persona que haya publicado un trabajo que, a juicio del CEC, resuelva plenamente las cuestiones planteadas por uno de los Problemas del Premio del Milenio, aunque no se ajuste exactamente a la redacción de la descripción oficial del problema."

En vista de que el CMI/SAB autoridad ejecutiva suprema la posibilidad lógica de modificar una pregunta del Premio del Milenio para dar cabida a $\Pi^0_1$ contraejemplos - a través del ingenioso " flechas ardientes ," para adoptar La frase de Dick Lipton y Ken Regan  - no puede excluirse formalmente.

Answer 1

$P\ne NP$ es un $\Pi^0_2$ declaración:

para cada polinomio $p$ y la máquina de Turing $M$ implementando un algoritmo que intente decidir el SAT, hay una fórmula $\phi_M$ de tal manera que si miramos el cálculo de $M$ en la entrada $\phi_M$ después de $p(|\phi_M|)$ pasos de cálculo, $M$ no se ha detenido o ha respondido incorrectamente.

( Editar : ha añadido más detalles a la $\Pi^0_2$ declaración anterior).

Si ponemos un límite computable al tamaño de $\phi_M$ en función de $M$ entonces podemos mejorar esto a un $\Pi^0_1$ y, por tanto, tendrá la propiedad $\text{undecidable}\rightarrow\text{true}$ , ya que es cierto $\Sigma^0_1$ Las afirmaciones son demostrables (en la Aritmética de Peano). Por supuesto, en un sentido formal, cualquier afirmación demostrable es equivalente a $0=0$ que es $\Pi^0_1$ .

¿Es plausible que eso $P\ne NP$ pero no existe un límite computable para $|\phi_M|$ ? Esto significaría que hay algoritmos que resuelven "arbitrariamente bien" el SAT en tiempo polinómico. Es decir, en relación con su descripción, son correctos para un nivel de función Ackermann o de función busy-beaver muchos $\phi$ 's.

Pero intuitivamente, no hay mucha estructura en SAT para explotar, y así una vez que tienes tantas variables $x_1,\ldots,x_v$ que una asignación aleatoria de valores de verdad tiene mayor complejidad de Kolmogorov que $M$ : $$K(M)\le v + O(1) $$ entonces debería haber un $\phi(x_1,\ldots,x_m)$ en el que $M$ falla. Como $K(M)$ tiene un límite computable como función de $M$ se deduce que $M\mapsto |\phi_M|$ está acotado computacionalmente. Esto es probablemente un "factor" en alguna parte; tal vez una mejor manera es decir que $P^A\ne NP^A$ para un oráculo aleatorio $A$ y en ese caso $\phi_M$ está acotado computacionalmente.

Así que podemos hacer una plausible " acotado computacionalmente $P\ne NP$ conjetura " que $M\mapsto \phi_M$ está acotado computacionalmente (con un límite específico incorporado en la conjetura), que sí tiene la propiedad $\text{undecidable}\rightarrow\text{true}$ .

Answer 2

La regularidad global para Navier-Stokes en el toroide es (lógicamente equivalente a) una $\Pi_2^0$ Esta es esencialmente una observación inédita de Bourgain (que la hizo en el contexto más general de las ecuaciones supercríticas), que he esbozado en este documento http://arxiv.org/abs/0710.1604 . Básicamente, Navier-Stokes equivale a la afirmación de que para todo $T, E > 0$ existe un $M$ de manera que todos los datos iniciales con $H^1$ norma a lo sumo $E$ existe una solución hasta el tiempo $T$ cuyo $H^1$ está siempre limitada por $M$ . Ahora bien, si tal afirmación es el caso, puede verificarse (utilizando una rigurosa teoría de la perturbación) construyendo un número suficiente de soluciones aproximadas para un número suficiente de elecciones de datos iniciales, y verificando que todas estas soluciones aproximadas tienen norma como máximo $M/2$ (decir) hasta el momento $T$ donde "número suficiente" es algo explícito que depende de $T, E, M$ y la naturaleza de la aproximación puede discretizarse a una escala explícita que también depende de $T,E,M$ . Por lo tanto, Navier-Stokes equivale a un enunciado de la forma $\forall T,E \exists M: P(T,E,M)$ donde $P(T,E,M)$ es algo que se puede verificar en tiempo finito para cada $T,E,M$ (que pueden tomarse como números racionales). (De hecho, para cada $E$ hay un tiempo explícito $T = T(E)$ para lo cual hay que verificar $P(T,E,M)$ y más allá de la cual la regularidad global se obtiene fácilmente a partir de la disipación de energía, por lo que la afirmación incluso se simplifica un poco a $\forall E \exists M: P( T(E), E, M)$ .)

Sin embargo, me parece muy difícil hacer que Navier-Stokes sea equivalente a un $\Pi^0_1$ declaración. Esto equivaldría básicamente a poder describir todos los posibles "escenarios de explosión" mediante un conjunto contable, y poder determinar si cada uno de esos escenarios de explosión puede realmente ocurrir en un tiempo finito. Mientras que algunos Los escenarios de explosión (particularmente los "estables", "aproximadamente autosimilares") pueden ser descritos y verificados de tal manera, no está claro si todo de ellos puede.

Answer 3

Como señaló Harry Altman, para una conjetura indecidible -> verdadero significa que se puede formular como un $\Pi_1^0$ declaración. En pocas palabras, si la conjetura es falsa, se puede demostrar mediante un cálculo explícito (finito). Yo dejaría Yang-Mills y Navier-Stokes a alguien más familiarizado con la física matemática que yo. Las otras tres conjeturas, aparentemente, no son $\Pi_1^0$ declaraciones por ahora.

Por cierto, la conjetura de Poincare no era una $\Pi_1^0$ declaración antes del algoritmo de Rubinstein (que determina si un 3manifold es o no la 3-esfera, ver el comentario de HJRW). (Expertos, corregidme aquí si me equivoco). Así que, si una conjetura particular está en esta categoría depende de los conocimientos disponibles. Al fin y al cabo, una vez que una conjetura se demuestra está en $\Pi_1^0$ por definición.

Permítanme comenzar con la conjetura de Birch y Swinnerton-Dyer. Técnicamente, lo que se necesita para obtener \$1M es demostrar o refutar lo siguiente ( http://www.claymath.org/millenium-problems/birch-and-swinnerton-dyer-conjecture ). Si $E$ es una curva elíptica sobre $\mathbb{Q}$ entonces $r = rank(E(Q))$ , llamado rango aritmético, es igual al orden $r_*$ de cero de $L(E, s)$ en $s=1$ , llamado rango analítico. Esta conjetura consta en realidad de dos partes bastante diferentes, a saber $r\le r_*$ y $r\ge r_*$ . La primera es a $\Pi_1^0$ declaración. Si $r>r_*$ para una curva determinada $E$ , se puede demostrar mediante un cálculo directo (con algo de suerte). La otra mitad de la conjetura es más complicada, como señaló Will Sawin. El problema es que no hay ningún algoritmo conocido para calcular el grupo $E(Q)$ . (No me malinterprete: hay algunos algoritmos, y aparentemente aparentemente funcionan. Sólo que no tenemos una prueba de que funcionen).
En teoría, es posible que mientras $r<r_*$ para alguna curva $E$ , nunca lo sabrás porque no estarás seguro de si hay más generadores de $E(Q)$ que aún no has encontrado. De hecho, Manin utilizó este mismo argumento en sentido contrario, y propuso una algoritmo de cálculo del grupo Mordell-Weil suponiendo que el Birch y el Swinnerton-Dyer (Véase Hindry, Silverman "Diophantine Geometry" para más detalles. Para ser pedante, se necesita un poco más entonces $r=r_*$ para esto).
Por lo tanto, la desigualdad $r\ge r_*$ no es un $\Pi_1^0$ declaración todavía, por lo que yo sé.

No puedo decir nada sensato sobre la conjetura de Hodge, excepto que definitivamente no parece $\Pi_1^0$ . Para refutarlo con un ejemplo explícito, hay que demostrar que en una variedad particular no hay ciclos algebraicos con una clase de cohomología dada. Quizá los expertos lo sepan mejor, pero nunca he oído hablar de ningún algoritmo para un trabajo como este.

Bjørn Kjos-Hanssen ya dio una respuesta sobre $P\neq NP$ y no tengo mucho que añadir. Excepto que, como señalé en otra pregunta, Cómo probar un $\Pi_2$ ¿se ha hecho bien la declaración? , existe la posibilidad técnica de que ese problema sea decidible, pero la "decisión" es errónea. (No me tomen en serio, no creo realmente en esto).