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

¿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?

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.$P\neq NP$

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

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 $n$$\mathsf{PHP}_n$$[n+1] \to [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).$\mathsf{P} \neq \mathsf{NP}$$s(n)$$s(n)$$n$

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 = NP$$P=NP$$O(1)$

• Del mismo modo, si existe una prueba de que , entonces podemos escribir un algoritmo que emite esta prueba en el tiempo O ( 1 ) .$P\neq NP$$O(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(\infty)$

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.

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.$n^{100}$