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álculo de aceptación 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]
⊕ P es una clase de conteo y se puede considerar que encuentra el 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, 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]
Si bien el teorema de Toda muestra que P PP contiene PH , no se sabe que P ⊕ P ni siquiera contenga 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. [3]
⊕ P contiene el problema de 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 uno o cero caminos de aceptación. En términos más generales, ⊕ P es bajo por sí mismo, lo que significa que una máquina de este tipo no gana poder al ser capaz de 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 booleana 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.