Complejidad de prueba de una prueba o prueba de P = NP

15

¿Ha habido alguna investigación sobre la complejidad de la prueba de una resolución al problema P = NP? Si no es así, dada la falta de progreso en el problema, ¿no sería razonable conjeturar que cualquier prueba que resuelva el problema P = NP requerirá un número súper polinómico de pasos?

Tony Johnson
fuente
18
Tal vez no entiendo su pregunta, pero cualquier resolución para P vs NP sería una prueba de tamaño constante, ¿sí?
Kurt Mueller
@Kurt Muller. La prueba requerirá un número súper polinómico de pasos basado en el número de símbolos que se requieren para codificar el problema P = NP.
Tony Johnson el
1
@TonyJohnson Superpolynomial en una constante sigue siendo una constante.
David Richerby el

Respuestas:

14

Se sabe que cualquier prueba de límites inferiores del circuito súper polinomial (que son declaraciones ligeramente más fuertes que ) requiere pruebas súper polinómicas, incluso exponenciales, en sistemas de prueba débiles como la resolución. Generalizar esto a sistemas de prueba más fuertes es un problema abierto bien conocido.PNP

Vea la sección 5 de esta encuesta de A. Razborov donde se muestran estas cosas.

Jan Johannsen
fuente
24

La complejidad de la prueba solo tiene sentido cuando hay una secuencia de declaraciones que dependen de un parámetro . Por ejemplo, la proposición P H P n establece (informalmente) que no hay biyección [ n + 1 ] [ n ]nPHPn[n+1][n] . Esta secuencia de proposiciones es difícil para ciertos sistemas de prueba proposicional.

La declaración es una declaración única, por lo que no puede aplicarle directamente la complejidad de la prueba. Sin embargo, la siguiente secuencia de declaraciones tiene sentido, para funciones particulares s ( n ) : "no hay circuito de tamaño s ( n ) que resuelva correctamente SAT para instancias de longitud n ". Esto ha sido considerado en la literatura, por ejemplo por Razborov (quien consideró el establecimiento de la complejidad de la prueba uniforme, es decir, la aritmética limitada).PNPs(n)s(n)n

Yuval Filmus
fuente
5

Tenemos 3 casos:

  • Existe una prueba de que . Entonces hay un algoritmo que resuelve el problema "Emitir una prueba de que P = N P " que se ejecuta en tiempo O ( 1 ) . Codifica la prueba en la máquina Turing y la emite. Se ejecuta al mismo tiempo sin importar su entrada.P=NPP=NPO(1)

  • Del mismo modo, si existe una prueba de que , entonces podemos escribir un algoritmo que emite esta prueba en el tiempo O ( 1 ) .PNPO(1)

  • Si no existe ninguna prueba de cualquiera de los casos, que la complejidad mínima de encontrar una prueba para cualquiera es : ninguna máquina de Turing nunca puede detener y emitirá un comprobante de cualquiera, ya que no existen tales pruebas.O()

El hecho de que no hayamos encontrado ninguna prueba no significa que no exista, y las clases de complejidad se definen en términos de lo que existe.

Más precisamente, no podemos saber con precisión cuán difícil es encontrar una prueba de o lo contrario hasta que sepamos el resultado, que de alguna manera derrota el punto.P=NP

Lo que sí sabemos es que, en general, el problema de "Tomar una declaración en la lógica de predicados y determinar si hay una prueba de ello" es indecidible. Por lo tanto, no existen procedimientos genéricos de generación de pruebas en los que podamos conectar P vs NP, que garanticen que produzcan un resultado.

jmite
fuente
-2

Si P = NP, entonces todo lo que necesita hacer es crear un algoritmo de tiempo polinómico para resolver algún problema de NP completo, y demostrar que en realidad es polinomial (lo que podría ser difícil, por ejemplo, el algoritmo Simplex generalmente se ejecuta muy rápido pero demostrando que corre rápido parece increíblemente difícil).

Ok, esto puede ser muy difícil. Supongamos que encontramos un algoritmo que supuestamente resuelve el problema del vendedor ambulante en O ( ). Difícil. Ni siquiera podemos medir el tiempo de ejecución de un problema con dos ciudades.n100

gnasher729
fuente
P=?NP? "
David Richerby
También existe el resultado (improbable pero totalmente posible) de que P = NP, pero no existe un algoritmo de tiempo polinomial uniformemente demostrable para, por ejemplo, SAT.
Steven Stadnicki