La dureza de generar una instancia de un problema que es más difícil que la complejidad del problema resultante.

En la película Inception, Cobb le pide a Ariadne que le pida que diseñe un laberinto que le tome el doble de tiempo. Esto se presta a un problema generalizado en el que tenemos una situación en la que los recursos están limitados por una cierta cantidad y quien verifique que este problema se encuentre en la clase de complejidad dada que tomará más tiempo o espacio para resolver. ¿Es este un problema nuevo?

Esta situación aparece con frecuencia en criptografía, donde desea generar instancias de problemas difíciles junto con sus soluciones. Por ejemplo, existe el trabajo de Eric Bach (y más tarde, Adam Kalai) sobre la generación eficiente de enteros aleatorios con sus factorizaciones principales.

Una de las muchas observaciones interesantes de Impagliazzo y Wigderson (Aleatoriedad versus tiempo: desrandomización bajo una suposición uniforme. J. Comput. Syst. Sci., 63: 672–688, 2001) es que uno puede generar eficientemente matrices aleatorias uniformes módulo p junto con sus permanentes (Piénselo ... use la auto-reducibilidad del permanente ...) Además, sabemos que el permanente es auto-reducible al azar . Entonces este es un ejemplo de un problema muy difícil para el cual podemos generar instancias resueltas de manera eficiente.

Primero, no creo que el protocolo Arthur-Merlin tenga que ingresar al modelo; parece que la motivación es que solo quieres producir instancias de problemas rápidamente para que cualquier algoritmo para resolverlos sea lento. En otras palabras, si pudiéramos demostrar que Arthur puede producir un problema difícil, entonces parece que Merlín no necesita verificar que el problema producido es difícil.

Muy relacionada está esta pregunta : ¿podemos generar en tiempo polinómico un lenguaje que no sea decidible en tiempo polinómico? La respuesta es sí si P unario no es igual a NP unario.

$f$$x$$f$$f(x)$$x$

$n$$n$$i$$\{1,\dots,n\}$$i$