¿Hay una tarea que se pueda resolver en tiempo polinómico pero que no se pueda verificar en tiempo polinómico?

Un colega mío y yo acabamos de tocar algunas notas de uno de nuestros profesores. Las notas indican que hay tareas que son posibles de resolver en tiempo polinomial (están en la clase de PF) pero que NO son verificables en tiempo polinomial (NO están en la clase de NPF).

Para elaborar sobre estas clases: obtenemos algo de entrada X y producimos algo de salida Y de tal manera que (X, Y) están en relación con R que representan nuestra tarea. Si es posible obtener Y para X en tiempo polinómico, la tarea pertenece a la clase de PF. Si es posible verificar el certificado de longitud polinómica Z que demuestra que una tupla (X, Y) está en relación con R en tiempo polinómico, la tarea pertenece a la clase de NPF.

No estamos hablando de problemas de decisión, donde la respuesta es simplemente SÍ o NO (más formalmente si alguna cadena pertenece a algún idioma). Para problemas de decisión, parece que PF es un subconjunto adecuado de NPF. Sin embargo, para otras tareas puede ser diferente.

¿Conoces una tarea que pueda resolverse en tiempo polinómico pero no verificada en tiempo polinómico?

complexity-theory np Drozi
fuente

Quizás no entiendo bien, pero ¿por qué el siguiente no es un algoritmo de verificación de tiempo polinomial? Dado

, calcule la función

usted mismo, utilizando el algoritmo de tiempo polinomial, y devuelva "correcto" si

. ¿Es posible que haya leído mal o que el profesor habló mal y haya querido decir que hay problemas verificables en el tiempo polinómico pero que no se pueden resolver en el tiempo polinómico?

(x, y)

$(x,y)$

f (x)

$f(x)$

f (x) = y

$f(x)=y$

Lieuwe Vinkhuijzen

@LieuweVinkhuijzen "¿decir que hay problemas verificables en el tiempo polinómico pero que no se pueden resolver en el tiempo polinómico?" [árbitro. necesario]

T. Verron

@ T.Verron Jaja sí, yo también estaría muy feliz de ver la prueba del profesor para este reclamo;)

Lieuwe Vinkhuijzen

Respuestas:

Esto solo es posible si hay muchas salidas admisibles para una entrada dada. Es decir, cuando la relación no es una función porque viola la unicidad. $R$

Por ejemplo, considere este problema:

Dado (representado en unario) y una TM , produzca otra TM tal que y (donde representa la codificación (número de Gödel) de en un número natural) $n \in \mathbb{N}$ $M$ $N$ $L(M)=L(N)$ $\# N > n$ $\# N$ $N$

Resolver esto es trivial: continúe agregando algunos estados redundantes al TM , posiblemente con algunas transiciones ficticias entre ellos, hasta que su codificación exceda . Esta es una aplicación básica repetida de Padding Lemma en TMs. Esto requerirá rellenos, cada uno de los cuales puede agregar un estado, por lo tanto, se puede hacer en tiempo polinómico. $M$ $n$ $n$

Por otra parte, dado es undecidable para comprobar si es una salida correcta para las entradas de . De hecho, verificar es indecidible (aplicar el teorema de Rice), y la restricción solo descarta finitamente muchos s de esos. Como eliminamos una cantidad finita de elementos de un problema indecidible, aún obtenemos un problema indecidible. $n,M,N$ $N$ $n,M$ $L(M)=L(N)$ $\#N > n$ $N$

También puede reemplazar la propiedad indecidible para obtener variaciones que todavía son computables pero NP duras / completas. Por ejemplo, dado (en unario) es trivial calcular una gráfica tiene una -clique dentro. Pero dado es difícil verificar si existe una -clique. $L(M)=L(N)$ $n$ $G$ $n$ $n,G$ $n$

chi
fuente

Se esperaba que este no fuera el caso. ¡Gran respuesta!

Filip Haglund

Esto no responde la pregunta. El OP solicitó específicamente un problema no verificable en el sentido habitual, donde, además de la entrada y la supuesta respuesta, obtenemos un certificado

que certifica la exactitud de la respuesta. En su caso, el certificado son los bits utilizados para generar de forma no determinista la nueva máquina Turing equivalente. Dada

, es fácil comprobar si

da la máquina

. Sin

, la pregunta es si es fácil generar instancias difíciles de lenguajes (NPC), lo cual solo es cierto en Minicrypt y Cryptomania.

z

$z$

M, N

$M, N$

z

$z$

z

$z$

M

$M$

z

$z$

Lieuwe Vinkhuijzen

@chi No todos los pares

pueden certificarse, pero el conjunto de pares

generado por su algoritmo puede certificarse. El certificado es la transcripción de su algoritmo que produce

partir de

(por ejemplo, "comience con

, luego agregue este estado y agregue esta transición, luego ... y voilà,

!"). En general, si

es un algoritmo no determinista que, dado

, siempre calcula una

admisible , entonces una transcripción de una ruta de cálculo de

es un certificado de que una

dada es admisible.

M, N

$M, N$

M, N

$M, N$

N

$N$

M

$M$

M

$M$

N

$N$

T

$T$

x

$x$

y

$y$

T (x)

$T(x)$

y

$y$

Lieuwe Vinkhuijzen

@chi Hay un ligero matiz en la pregunta: ¿Para una relación arbitraria

, es posible que no todos admisible

son certificables, y le dará un ejemplo elegante. Sin embargo, la pregunta no pregunta si existen relaciones admisibles pero no certificables (la respuesta es sí , por su ejemplo), sino que pregunta si podemos tener un algoritmo que produzca resultados no certificables admisibles. La respuesta, aquí, debe ser no , debido al argumento anterior.

R

$R$

y

$y$

Lieuwe Vinkhuijzen

@chi No sé qué pretendía preguntar el OP, pero encontré su respuesta muy esclarecedora, ¡aprendí algo! En mi opinión, la pregunta puede leerse de la manera que usted lo hace, o igualmente plausible como " ¿existen funciones unidireccionales? " (tal vez) o "¿ son fáciles de generar instancias difíciles de problemas NP? " (espero que así sea para RSA), o, la forma en que lo leí, como " ¿Es ? $NP\subsetneq P$ " (no).

Lieuwe Vinkhuijzen

Esto es simplemente una elaboración de la primera oración de la respuesta de @ chi, ya que no lo encontré obvio.

La idea es que si tiene un algoritmo que encuentra la respuesta a algún problema en tiempo polinómico, entonces hay dos posibilidades:

Anteriormente ha demostrado (matemáticamente) que la salida del algoritmo es una solución al problema, en cuyo caso, los pasos del algoritmo en sí mismos constituyen la prueba de corrección.
Tiene un algoritmo diferente para verificar que la salida es realmente una solución, en cuyo caso debe estar ejecutando este algoritmo (de lo contrario, estaría en el caso n. ° 1), lo que implica que lo está haciendo en tiempo polinómico.

Por lo tanto, no puede haber tal problema.

Mehrdad
fuente

I don't understand #2. What implies that the different algorithm runs in polynomial time?

Albert Hendriks

@AlbertHendriks: If the verifier didn't run in polynomial time then the original solver could not claim to have found a correct solution in polynomial time, because it needs to run the verifier to make sure its solution is correct.

Mehrdad