¿Qué pasa si el problema (P vs NP) es en sí mismo un problema NP-Hard?

Es un problema de decisión después de todo, ¿verdad?

No en el sentido que quieres decir, no.

Los problemas de decisión que pertenecen a las clases de complejidad P y NP pueden tomar un número infinito de entradas posibles. La dificultad no está en encontrar una respuesta para una entrada en particular, después de todo, eso se puede determinar de antemano y luego codificar, sino en encontrar un algoritmo que funcione para entradas arbitrariamente grandes.

El problema P vs NP no es así en absoluto. Es una sola pregunta, y la respuesta es “sí” o “no”. (O posiblemente “hay ciertos modelos de ZFC en los que esto es cierto, y otros en los que es falso”, pero si ese fuera el caso, diría que simplemente significaría que nos estamos perdiendo un axioma muy necesario).

Puede que no (con una excepción). porque si un problema es NP-hard entonces su tiempo de resolución es exponencial al tamaño de entrada, eso significa que para n = 1 el tiempo de resolución es constante, en ese caso para el problema PvsNP NP podemos dar un solo problema NP-hard (entonces n = 1 ) como entrada y resolverlo en tiempo constante y eso resuelve todo el problema PvsNP. Dos excepciones (editar: solo una válida) son
1. Costant sí mismo es muy grande o
2. la base del exponente es un gran polinomio u otra función exponencial (pero en cuyo caso el problema pertenece a otra clase en lugar de NP)

Bueno, P vs NP tiene una sola respuesta *, Sí o No. Si supiéramos esa respuesta, podríamos escribir fácilmente un programa para “calcular” esa respuesta. Entonces, en ese sentido, no, el problema P vs NP no es NP-difícil.

Sin embargo, hay un problema relacionado, que es el siguiente: dado un conjunto de axiomas y un teorema, ¿se sigue el teorema de los axiomas?

Bueno, podríamos escribir P = NP como una declaración lógica formal, ingresarlo junto con los axiomas ZFC (o sus favoritos) y obtener la respuesta a P vs NP. Entonces, este es probablemente el problema de decisión no trivial más natural que realmente nos permite resolver P vs NP.

Resulta que este problema es NP-hard, y de hecho, es indiscutible.

(*) Bueno, supongo que P vs NP podría ser independiente de ZFC por lo que sé, y luego debes ser un poco más cuidadoso aquí. Ignoraré tales tecnicismos.

La prueba es indecidible porque hay declaraciones que no tienen una prueba ni una refutación. Si se limita a la clase de enunciados de valor de verdad, y no está claro que P vs NP esté entre esos, obtendrá al menos tiempo exponencial, porque uno puede construir tautologías con un tamaño de prueba exponencial ( http: //users.math.cas .cz / ~ pudlak …), y solo escribir la prueba lo pondrá en EXPTIME.

Entonces, ¿qué tal si primero responde NP vs EXPTIME, luego podemos discutir si la prueba está en NP o no?

P vs NP es un problema de decisión, pero mostraré que está en P. Ahora intentaré dar una solución que responda al problema P vs NP: dado que el problema no toma ninguna entrada, no hay ningún parámetro que pasar en.

bool P_equals_NP () {
devuelva SÍ;
}

o

bool P_equals_NP () {
devolver NO;
}

Se ejecuta en tiempo constante! Por lo tanto, P vs NP está en P. El único problema es que todavía no hemos sabido qué código es correcto (pero uno de ellos será correcto).