¿Los conjuntos de contención más conocidos para / por NP y Parity-P?

18

Parity-P es el conjunto de lenguajes reconocidos por una máquina de Turing no determinista que solo puede distinguir entre un número par o un número impar de rutas de "aceptación" (en lugar de un número cero o no cero de rutas de aceptación). Por lo tanto Paridad-P es básicamente PP atrofiado hermano más joven 's: mientras que los recuentos de PP si o no el número de caminos que aceptan de un NP-máquina es una mayoría o no ( es decir, el bit más significativo de dicha cantidad), la paridad-P indica el bit menos significativo del número de rutas de aceptación.

Al igual que NP, Parity-P contiene UP (que contiene P, "probablemente" estrictamente); y como NP, Parity-P está contenido en PSPACE.

Pregunta. ¿Cuáles son los límites superiores e inferiores conjuntos más conocidos para NP y Parity-P?

cc.complexity-theory complexity-classes np Niel de Beaudrap
fuente

Respuestas:

17

Por Valiant-Vazirani, NP está contenido en BP dot Parity-P (que obviamente contiene Parity-P). Además, Toda demostró que PH está en BP dot Parity-P que está en P ^ (# P) (que está en PSPACE).

Para los límites inferiores, creo que ambas clases contienen una clase conocida como FewP que contiene UP y es como NP, pero usted pregunta que las cadenas en el lenguaje tienen polinomialmente muchas rutas de aceptación.

[Actualización: error tipográfico corregido BPP en lugar de BP]

Manu
fuente
55
Un corolario de la contención PH en BPP dot Parity-P, es que Parity-P no está contenido en la Poly Hierarchy a menos que esa Jerarquía se colapse.
Andy Drucker
44
Esto se debe a que, si Parity-P está en Sigma_k-P, entonces PH está en el punto BPP Sigma_k-P, que está contenido en Pi_ (k + 1) -P. (esta última contención se deriva de una generalización directa del "operador" del resultado de que BPP está en la intersección Sigma_2 P Pi_2 P.)
Andy Drucker
44
Creo que se considera plausible que BPP dot Parity-P esté contenido en P ^ (Parity-P). Si esto es cierto, entonces PH está contenido en P ^ (Paridad), que está contenido en (Paridad-P) ^ (Paridad-P), que en realidad es igual a Paridad-P. De lo que no estoy seguro es de si algún documento sobre dureza versus aleatoriedad da una hipótesis que implique la paridad de puntos BPP-P contenida en P ^ (paridad-P).
Andy Drucker
44
Finalmente, Parity-P se distingue de NP y otras clases de PH en que se sabe que tiene reducciones del peor de los casos al caso promedio. Es decir, si Parity-P no está en P, entonces contiene problemas de distribución que son difíciles de entender. Ver Feigenbaum-Fortnow, "Auto-reducibilidad aleatoria de conjuntos completos".
Andy Drucker
3
Aquí está la idea general: dejar que C sea una clase de complejidad. Un lenguaje L está en (BPP punto C) si existe un lenguaje S en C, que consiste en pares codificados (x, r), de modo que: -si x está en L, entonces para 2/3 de todo r, el par (x, r) está en S; -si x no está en L, entonces para 2/3 de todo r, el par (x, r) no está en S. (Técnicamente, la longitud de r depende de x y se requiere que sea como máximo algún polinomio en | x |.)
Andy Drucker