En la teoría de la complejidad computacional , la clase de complejidad ⊕ P (pronunciada "paridad P") es la clase de problemas de decisión que puede resolver una máquina de Turing no determinista en tiempo polinomial, donde la condición de aceptación es que el número de rutas de cómputo aceptadas sea impar. Un ejemplo de un problema de ⊕ P es "¿un gráfico dado tiene un número impar de coincidencias perfectas ?" La clase fue definida por Papadimitriou y Zachos en 1983. [1]
⊕ P es una clase de conteo y puede considerarse que encuentra la parte menos significativa de la respuesta al problema #P correspondiente . El problema de encontrar el bit más significativo está en PP . Se cree que PP es una clase considerablemente más dura que ⊕ P ; por ejemplo, hay un universo relativizado (ver máquina oráculo ) donde P = ⊕ P ≠ NP = PP = EXPTIME , como lo muestran Beigel, Buhrman y Fortnow en 1998. [2]
Mientras que el teorema de Toda muestra que P PP contiene PH , no se sabe que P ⊕ P contenga NP . Sin embargo, la primera parte de la demostración del teorema de Toda muestra que BPP ⊕ P contiene PH . Lance Fortnow ha escrito una prueba concisa de este teorema. [3]
⊕ P contiene el problema isomorfismo gráfico , y de hecho este problema es bajo para ⊕ P . [4] También contiene trivialmente UP , ya que todos los problemas en UP tienen cero o una ruta de aceptación. De manera más general, ⊕ P es bajo por sí mismo, lo que significa que dicha máquina no gana potencia al poder resolver cualquier problema de ⊕ P al instante.
El símbolo ⊕ en el nombre de la clase puede ser una referencia al uso del símbolo ⊕ en el álgebra de Boole para referirse al operador de disyunción exclusivo . Esto tiene sentido porque si consideramos "acepta" como 1 y "no acepta" como 0, el resultado de la máquina es la disyunción exclusiva de los resultados de cada ruta de cálculo.
enlaces externos
Referencias
- ^ CH Papadimitriou y S. Zachos . Dos comentarios sobre el poder de contar . En Proceedings of the 6th GI Conference in Theoretical Computer Science , Lecture Notes in Computer Science , volumen 145, Springer-Verlag, págs. 269–276. 1983.
- ^ R. Beigel, H. Buhrman y L. Fortnow . Es posible que NP no sea tan fácil como detectar soluciones únicas. En Actas de ACM STOC'98 , págs. 203–208. 1998.
- ^ Fortnow, Lance (2009), "Una prueba simple del teorema de Toda", Teoría de la Computación , 5 : 135-140, doi : 10.4086 / toc.2009.v005a007
- ^ Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1992), "Graph isomorphism is low for PP", Computational Complexity , 2 (4): 301–330, doi : 10.1007 / BF01200427.