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 se pueden resolver mediante una máquina de Turing no determinista en tiempo polinomial, donde la condición de aceptación es que el número de caminos de cómputo que aceptan es impar. Un ejemplo de un problema ⊕ P es "¿tiene un gráfico dado un número impar de coincidencias perfectas ?". La clase fue definida por Papadimitriou y Zachos en 1983. [1]
Un ejemplo de un problema ⊕ P -completo (bajo reducciones de muchos-uno ) es ⊕SAT: dada una fórmula booleana, ¿es impar el número de asignaciones que la satisfacen? Esto se desprende del teorema de Cook-Levin porque la reducción es parsimoniosa . [2]
⊕ P es una clase de conteo, y puede verse como la búsqueda del bit menos significativo 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 difícil que ⊕ P ; por ejemplo, existe un universo relativizado (ver máquina oráculo ) donde P = ⊕ P ≠ NP = PP = EXPTIME , como lo demostraron Beigel, Buhrman y Fortnow en 1998. [3]
Si bien el teorema de Toda muestra que P PP contiene PH , no se sabe que P ⊕ P contenga siquiera NP . Sin embargo, la primera parte de la prueba del teorema de Toda muestra que BPP ⊕ P contiene PH . Lance Fortnow ha escrito una prueba concisa de este teorema. [4]
⊕ P contiene el problema de automorfismo de grafos y, de hecho, este problema es bajo para ⊕ P . [5] También contiene trivialmente UP , ya que todos los problemas en UP tienen caminos de aceptación de cero o uno. De manera más general, ⊕ P es bajo para sí mismo, lo que significa que una máquina de este tipo no gana poder al poder resolver cualquier problema de ⊕ P instantáneamente.
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 exclusiva . Esto tiene sentido porque si consideramos que "acepta" es 1 y "no acepta" es 0, el resultado de la máquina es la disyunción exclusiva de los resultados de cada ruta de cálculo.