Si P = NP, ¿podríamos obtener pruebas de la Conjetura de Goldbach, etc.?

Esta es una pregunta ingenua, por mi experiencia; disculpas de antemano.

La Conjetura de Goldbach y muchas otras preguntas no resueltas en matemáticas se pueden escribir como fórmulas cortas en cálculo de predicados. Por ejemplo, el artículo de Cook "¿Pueden las computadoras descubrir rutinariamente pruebas matemáticas?" formula esa conjetura como

\forall n [(n > 2 \land 2 | n) \supset \exists r \exists s (P (r) \land P (s) \land n = r + s)]

$\forall n [( n > 2 \wedge 2 | n) \supset \exists r \exists s (P(r) \wedge P(s) \wedge n = r + s) ]$

Si restringimos la atención a las pruebas polinomialmente largas, entonces los teoremas con tales pruebas están en NP. Entonces, si P = NP, podríamos determinar si, por ejemplo, la Conjetura de Goldbach es verdadera en el tiempo polinómico.

Mi pregunta es: ¿también podríamos exhibir una prueba en tiempo polinómico?

Editar . Según los comentarios de Peter Shor y Kaveh, debería haber calificado mi afirmación de que podríamos determinar si la conjetura de Goldbach es verdadera si es uno de los teoremas con una prueba corta. Que por supuesto no sabemos!

cc.complexity-theory proof-complexity automated-theorem-proving proof-search Joseph O'Rourke
fuente

Primero, para exhibir una prueba corta (¿<1000 páginas?) De la conjetura de Goldbach, tiene que haber una prueba corta. P = NP no tiene relación con eso.

Peter Shor

@Suresh, @Kaveh: Parece que te estás equivocando. Aquí tenemos una instancia concreta de un problema de búsqueda de NP. El cuantificador que es relevante aquí es la existencia de una prueba (en un sistema formal adecuado) del teorema.

Kristoffer Arnsfelt Hansen

Otra observación es que en realidad podemos escribir un algoritmo, que si P = NP encontrará una prueba para una declaración dada si existe en el tiempo polinomio en la longitud de la declaración y la longitud de la prueba más corta. (Este polinomio es un límite que se cumple para todos los teoremas). Sin embargo, será un algoritmo "astronómico".

Kristoffer Arnsfelt Hansen

@ Joe: ¡No, en realidad puedo escribir el algoritmo ahora mismo! (Incluso sin saber si P = NP). La idea es lo que se conoce como la búsqueda universal de Levin.

Kristoffer Arnsfelt Hansen

@ Kristoffer: ¡Genial! No sabía sobre LS. Veo que Marcus Hutter tiene una especie de mejora en LS: "El algoritmo más rápido y más corto para todos los problemas bien definidos". Revista Internacional de Fundamentos de Ciencias de la Computación, 13 (3): 431-443, 2002.

Joseph O'Rourke

Respuestas:

¡En efecto!

Si P = NP, no solo podemos decidir si existe una prueba de longitud n para la Conjetura de Goldbach (o cualquier otra afirmación matemática), sino que también podemos encontrarla de manera eficiente.

¿Por qué? Porque podemos preguntar: ¿hay una prueba condicionada en el primer bit ..., entonces, hay una prueba condicionada en los dos primeros bits ..., y así sucesivamente ...

¿Y cómo sabrías n? Simplemente probará todas las posibilidades, en orden creciente. Cuando damos un paso en la i-ésima posibilidad, también intentamos un paso en cada una de las posibilidades 1 .. (i-1).

Dana Moshkovitz
fuente

¿No es este el algoritmo de búsqueda universal de Levin?

Mohammad Al-Turkistany

@turkistany: sí, lo es!

Dana Moshkovitz

Dana ha respondido la pregunta. Pero aquí hay algunos comentarios en el lado práctico.

$P=NP$ $P=NP$ $P=coNP$

$NP$ $l$ $P=NP$ $l$

$P=NP$ $l$ $l$ $P=NP$ $P$ $DTime(n^2)$ ), entonces uno puede tomar este algoritmo y ejecutarlo para verificar las pruebas de una longitud factible pero muy grande que será más grande que cualquier prueba que cualquier humano pueda encontrar, y si el algoritmo no encuentra una respuesta, entonces el La oración es prácticamente imposible de probar. El truco que Dana ha mencionado también funcionará aquí para encontrar la prueba.

Por medios prácticos:

$P=NP$ $DTime(10000n^{10000})$
encontrará una prueba solo si hay una (es decir, la oración no es una oración indecidible en ZFC), además, la prueba debe ser factiblemente corta.
$P\neq NP$ $NP=DTime(n^{\log^* n})$ .

Kaveh
fuente

(n^{10})

$(n^{10})$