¿Hay algún problema que sea fácil de calcular pero difícil de verificar?

Suponiendo que P NP, los problemas de NP completo son "difíciles de resolver, pero tienen respuestas que son fáciles de verificar". ¿Tiene algún sentido considerar lo contrario, es decir, problemas para los cuales es fácil calcular una respuesta correcta, pero difícil de verificar una supuesta solución arbitraria? $\neq$

Creo que tal problema implicaría:

Exponencialmente muchas respuestas "correctas" para cualquier entrada dada, porque de lo contrario la verificación podría llevarse a cabo simplemente calculando todas las respuestas correctas.
Algunas respuestas "correctas" son fáciles de calcular, pero otras son difíciles de encontrar.

complexity-theory rphv
fuente

Lo dudo. Si una respuesta es fácil de calcular, la elección del certificado es fácil: proporcione la supuesta respuesta con el problema y "verifique" la respuesta resolviendo el problema, y ver si la respuesta pretendida es realmente la respuesta.

Patrick87

@ Patrick87 - Creo que abordé esto en la pregunta. ¿Qué pasa con una función de valores múltiples que asocia un conjunto de valores con una entrada ? Suponga que , y que es fácil elegir un elemento de , pero dado es difícil determinar si .

f

$f$

I_{f} (x) = {y_{1}, y_{2}, \dots}

$I_f(x) = \{y_1, y_2, \dots \}$

x

$x$

| I_{f} (x) | = 2^{| x |}

$|I_f(x)| = 2^{|x|}$

I_{f} (x)

$I_f(x)$

z

$z$

z \in I_{f} (x)

$z \in I_f(x)$

rphv

@ Patrick87 El solucionador puede ser determinista y generar solo una de todas las respuestas existentes. Luego necesita una forma eficiente de verificar si dos soluciones son equivalentes. ¿Puede la equivalencia en un conjunto ser más difícil que resolver un problema en él?

Raphael

Realmente me perdí esa parte, lo siento. Aún así, me inclino a dudar de la premisa. Lo pensaré un poco más y volveré si tengo pensamientos más pertinentes.

Patrick87

Un certificado generalmente significa que hay una manera fácil de reconstruir una prueba, por lo que, por definición, si proporciona un certificado, la verificación es fácil. Una solución sin un certificado puede ser difícil.

Gilles 'SO- deja de ser malvado'

Respuestas:

Si está bien con problemas artificiales, puede hacer muchos de ellos. Aquí hay algunos:

Dado un entero positivo n en unario, responda una fórmula satisfactoria de 3CNF en n variables booleanas.
Dar una fórmula 3CNF satisfactoria es fácil, pero decidir si una fórmula 3CNF dada es satisfactoria o no es 3SAT, un problema NP-completo bien conocido.
No hay entrada Simplemente responda una máquina de Turing que se detiene (cuando se ejecuta con una cinta de entrada vacía).
Dar una máquina de Turing de este tipo es fácil, pero no se puede determinar si una máquina de Turing se detiene o no.

Agregado : Por cierto, no creo que lo que escribiste en el último párrafo tenga:

Creo que tal problema implicaría exponencialmente muchas respuestas "correctas" para cualquier entrada dada, porque de lo contrario la verificación podría llevarse a cabo simplemente calculando todas las respuestas correctas.

Si el problema tiene una solución, entonces verificar una respuesta no es más difícil que calcular la solución correcta. Sin embargo, si el problema tiene una solución fácil y una solución difícil, entonces no puede calcular todas las soluciones de manera eficiente. Aquí hay uno de esos problemas (que es muy artificial):

Dada una máquina de Turing M , responda una de las siguientes afirmaciones que es verdadera: " M se detiene en la cinta de entrada vacía", " M no se detiene en la cinta de entrada vacía" y " M es una máquina de Turing".
Dar una solución es fácil : siempre puede elegir " M es una máquina de Turing". Sin embargo, si una respuesta dada es correcta o no es indecidible. Tenga en cuenta que en este problema, solo hay dos soluciones para cada instancia.

Tsuyoshi Ito
fuente

¿Existe una manera razonable de definir formalmente lo que significa que tales problemas sean "artificiales"? (Por “razonable”, me refiero a algo que podemos acordar ampliamente, como decir que una definición de “computable” capta la intuición de lo que debería significar.)

Gilles 'SO- estar parada mal'

@Gilles: No, no lo creo. Llamé a estos problemas "artificiales" porque es muy poco probable que alguien encuentre estos problemas primero y luego descubra que es fácil dar una respuesta y difícil decidir la corrección de un candidato de respuesta dado. Pero esta "artificialidad" no es en absoluto una noción rigurosa.

Tsuyoshi Ito

@ Tsuyoshi Ito - Gracias por su respuesta clara. He editado el último párrafo para reflejar su visión.

rphv

Aunque la respuesta de Tsuyoshi Ito cubre la respuesta "principal", había dos notas más sutiles que quería agregar.

Incluso cuando la solución es difícil de verificar, verificar la solución sigue siendo fácil de verificar con una cadena de prueba corta. Es decir, al extender la solución un poco con información adicional, se vuelve fácilmente comprobable; la verificación siempre está en NP. Una forma de ver esto es que el agente que calcula una solución puede registrar todos los bits aleatorios que usa, y luego el verificador puede usar esa misma cadena aleatoria para ejecutar el mismo cálculo. (El probador debe usar bits aleatorios, de lo contrario, siempre emiten la misma respuesta, y el verificador siempre puede verificar fácilmente calculando una respuesta con el mismo método).
Para las computadoras cuánticas, esta es una pregunta muy abierta. Para las computadoras clásicas, el verificador siempre puede hacer algo como simular el probador y verificar que obtengan la misma respuesta. Es completamente posible que para algún problema complicado, exista un algoritmo cuántico que produzca una distribución uniforme en todas las soluciones (exponencialmente muchas), que son difíciles de verificar. No puede volver a ejecutar el probador, porque lo más probable es que obtenga una respuesta diferente cada vez.

Como ejemplo de un tipo similar de problema, el problema de Deutsch-Jozsa sufre un poco de esto. Si un oráculo no es una función equilibrada, entonces una computadora cuántica puede determinar rápidamente que este es el caso, pero no hay pruebas cortas que permitan que una computadora clásica verifique esto. (Esto es solo un problema "similar" porque todavía puede ser verificado por otra computadora cuántica, y la verificación también está en BPP clásico, incluso si no está en P.)

Alex Meiburg
fuente