¿Es útil un oráculo si no puede controlar las instancias de entrada?

8

Digamos F es un oráculo para un problema en NP, pero no puedo llamar a este oráculo con ninguna instancia de entrada. En cambio, cada vez que llamoFMe devuelven una instancia y solución al azar. Por lo tanto, sé queF de hecho es capaz de resolver arbitrarias NP-problemas difíciles, simplemente no puedo especificar cuál quiero que resuelva.

¿Es posible usar tal oráculo para resolver un NP-completa el problema más rápido? Mi instinto dice que no porque el uso ingenuo del oráculo todavía requiereO(2n)tiempo llamando al oráculo lo suficiente como para verificar cada solución. Simplemente no puedo pensar en una forma de probar esto.

Mike Izbicki
fuente
2
Quizás debería modificar la pregunta de esta manera: "... cada vez que llamo FMe devuelven una instancia aleatoria de tamaño n con distribución uniforme ... "(donden es el tamaño de la entrada de la máquina de Turing que puede acceder F)
Vor
@Vor, también pensé en agregar esa estipulación, pero no estoy seguro de que realmente marque la diferencia. Incluso si la distribución fuera tal que permitiera un número polinómico de llamadas para obtener ciertas instancias, aún requeriría más que llamadas polinómicas para obtener una gran mayoría de instancias. Creo que lo único que importa es que la distribución es que de alguna manera no puedo alterar la distribución para sesgarla a favor de mi instancia específica.
Mike Izbicki
1
Estoy de acuerdo con usted, pero sin un enlace / distribución "instancia aleatoria" no tiene sentido.
Vor
1
Creo que con "más rápido" te refieres a "en P" pero quizás quieras preguntar si está en BPP .
Xodarap
@Xodarap Estoy más interesado en un método para usar tal oráculo para convertir de cualquier clase (hipotéticamente) más compleja en una clase más débil. No necesariamente NP -> P. Además, no veo particularmente cómo las clases probabilísticas serían útiles.
Mike Izbicki

Respuestas:

8

Como señaló Xodarap, si necesita que su algoritmo con el "oráculo aleatorio" siempre muestre la respuesta correcta, entonces el oráculo aleatorio es inútil. El problema se vuelve más interesante si permitimos una pequeña probabilidad de error (donde la probabilidad es con respecto a la instancia aleatoria elegida por el oráculo).

Además, como Vor señaló en los comentarios sobre la pregunta, no tiene sentido decir "instancia aleatoria" sin especificar una distribución de probabilidad. Una de las suposiciones razonables para hacer aquí es que esta instancia aleatoria se elige uniformemente al azar del conjunto de todas las cadenas de longitud p ( n ), donde n es la longitud de entrada y p es un polinomio fijo. Podríamos hacer otras suposiciones más débiles sobre la distribución de probabilidad.

Aquí haremos la suposición bastante general, y mostraremos que la existencia de un algoritmo de tiempo polinomial aleatorio con un "oráculo aleatorio" para problemas de NP completo tiene una consecuencia sorprendente incluso bajo esta suposición débil.

Dejemos de lado el requisito de que el "oráculo aleatorio" resolverá un problema en NP (en una instancia elegida aleatoriamente). Ahora el "oráculo aleatorio" puede ser cualquier distribución de probabilidad predeterminada sobre cadenas de longitud polinómica, y cada vez que se le pregunta, emite una cadena de acuerdo con esta distribución de probabilidad. El único requisito es que esta distribución de probabilidad depende solo de la longitud de entrada. Tenga en cuenta que su modelo es de hecho un caso especial de este modelo. En su modelo, se requiere que la distribución de probabilidad tenga la siguiente forma: primero elige una instancia uniformemente aleatoria y de un conjunto dependiendo de la longitud de entrada, y luego devuelve un par ( y , g ( y )), donde g: {0, 1} * → {0, 1} es la función característica de algún problema de decisión en NP. Ahora permitimos cualquier distribución de probabilidad, siempre que la distribución esté determinada solo por la longitud de entrada.

Un "oráculo" de esta forma general se llama un consejo aleatorio . La clase de problemas de decisión que pueden resolverse mediante un algoritmo de tiempo polinómico aleatorio con un consejo aleatorio (con error de dos lados delimitado) se llama BPP / rpoly, y se sabe que esta clase es igual a P / poli . (La inclusión BPP / rpoly⊆P / poly se puede probar de la misma manera que una inclusión BPP⊆P / poly bien conocida. Para una prueba de esto último, véase, por ejemplo, el Teorema 6.3 de Goldreich [Gol08]).

Esto significa que si un problema NP-complete se puede resolver en su modelo, entonces NP⊆P / poly. Sin embargo, se sabe que NP⊆P / poly implica que la jerarquía polinómica se colapsa al segundo nivel [KW98, Cai07]. La mayoría de los teóricos de la complejidad consideran que un colapso de la jerarquía polinómica es una gran sorpresa. Si creemos que la jerarquía polinómica no colapsa, entonces los problemas de NP completo no pueden resolverse eficientemente con el "oráculo aleatorio" en su sentido.

Referencias

[Cai07] Jin-Yi Cai. S 2 p ⊆ ZPP NP . Journal of Computer and System Sciences , 73 (1): 25–35, febrero de 2007. DOI: 10.1016 / j.jcss.2003.07.015 .

[Gol08] Oded Goldreich. Complejidad computacional: una perspectiva conceptual . Cambridge University Press, 2008.

[KW98] Johannes Köbler y Osamu Watanabe. Nuevas consecuencias del colapso de NP teniendo pequeños circuitos. SIAM Journal on Computing , 28 (1): 311–324, 1998. DOI: 10.1137 / S0097539795296206 .

Tsuyoshi Ito
fuente
0

Pensemos específicamente en el problema NP-completo favorito de todos: 3SAT.

Es posible (aunque poco probable) que cada vez que llame a su oráculo le asigne una tarea para la misma instancia. Específicamente, cada vez podría darte una tarea para la oración trivial:

(xxx)(xxx)

Pero ya sabes la tarea para esto. Entonces su Oracle no puede ser útil.

Más formalmente, si llamamos a tu oráculo A, entonces PANP (asumiendo PNP...)

Xodarap
fuente
No significaría que dos instancias de 3SAT sean polinomiales reducibles en el tiempo. Solo que son reducibles en el tiempo polinomial dado un oráculo de instancia aleatoria. ¿Derecha?
Mike Izbicki
Aclarado; avíseme si no entiendo lo que quiere decir con "oráculo de instancia aleatoria".
Xodarap
Bueno, tomará un número exponencial de llamadas para obtener una asignación para la misma instancia. ¡De hecho, tomará tantas llamadas como sea necesario para obtener una asignación al problema particular que estoy tratando de resolver! Estás desechando todo ese trabajo, y puede haber alguna forma inteligente de utilizarlo.
Mike Izbicki
@ Mike: la complejidad se refiere al peor de los casos . Como en el peor de los casos el oráculo es inútil (como se muestra arriba), eso es todo lo que necesitamos saber.
Xodarap