Caracterizan P ^ NP

Question

¿Qué puede decir acerca de la clase de complejidad P ^ NP, es decir, decisión problemas solubles por un polytime TM con un oráculo para el SAT?

Obviamente P ^ NP en el PH en alguna parte entre coNP Unión NP y Sigma2 intersectar Pi2. ¿Qué más se sabe sobre esa clase de complejidad?

Answer 1

El estándar de problemas para la función de "versión" de la P^NP es encontrar la lexicográficamente último la satisfacción de la asignación de una determinada fórmula booleana. Para ser más meticuloso, un completo lenguaje para la P^NP es

{ n-variable booleana fórmulas phi phi es válido y phi lexicográficamente último la satisfacción de asignación ha x_n = 1 }.

Este es Krentel del Teorema.

Bajo un estándar de la complejidad de la suposición de que uno puede derandomize el más potente de la clase BPP^NP abajo a P^NP. Con el poder de la BPP^NP, uno puede calcular el número de satisfacer las asignaciones a un circuito dentro de un 1 +/- 1/poli(n) factor de [Sipser / Stockmeyer / Valiant-Vazirani] y exactamente aprender desconocido polinomio de tamaño de circuitos [Bshouty-Cleve-Gavalda-Kannan-Tamon].

Answer 2

Aquí hay otro interesante caracterización de $P^{NP}$. Me pareció una licenciatura pero no podía publicarlo; resultó ser un "folclore". Es entretenida sin embargo, y usted tendrá la oportunidad de aprender acerca de $P^{NP}$ por convencer por sí mismo. Vamos a definir un natural modelo determinista de la computación cuya clase de idiomas reconocidos de la se $P^{NP}$.

Una máquina de $M$ en nuestro modelo se describe como sigue. Nos tomamos un polinomio de tiempo de máquina de Turing que en una entrada de longitud $n$, se concede el acceso a un contador de bits que contiene $n^k$ bits, para algunos fijos $k$. Inicialmente, el contador es todo ceros. Junto con la costumbre de inicio, aceptar y rechazar a los estados, la máquina de Turing tiene un especial estado llamado de incremento, con las siguientes propiedades:

• Si la máquina de Turing entra en el incremento de estado, el contador se incrementa en $1$, y la máquina de Turing se restablece a su partida inicial de configuración. Es decir, todo el espacio de trabajo utilizado por la máquina se restablece a los espacios en blanco, todas las cabezas de la cinta volver al principio de la cinta, y la máquina se conecta a su inicio.
• Si la máquina de Turing se llega a aceptar o rechazar, todo el proceso se detiene con este resultado.
• Si el contador llega a todo, el proceso rechaza.

Esta es una forma natural para caracterizar la búsqueda de fuerza bruta para un NP solución: el contador representa el espacio de búsqueda, y le damos a ejecutar un determinado polytime máquina de Turing que las pruebas de cada valor de contador en el giro hasta que nos decidimos a aceptar o rechazar.

Teorema: La clase de todos los idiomas reconocidos por dicho $M$ es exactamente $P^{NP}$.

Buena suerte con la prueba. He aquí una sugerencia: una dirección es fácil, por Ryan O'Donnell comentario completo en idiomas para $P^{NP}$.

Answer 3

Esta clase también es conocida como Δ₂P. Ver el zoo de la complejidad para más detalles y resultados.

Answer 4

Creo que MAX_CLIQUE_SIZE es en $P^{NP}$. Clase de problemas que son reducibles a Cook a $NP$ problemas. Algo estrechamente relacionado con el estaba en una que pregunta abierta enviado de mi prof de complejidad de cómputo real :)