⊕P
En teoria de la complexitat, la classe de complexitat ⊕P (pronunciada "P paritat") és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing no determinista en temps polinòmic, on la condició d'acceptar és que el nombre de camins de computació sigui senar.

També es pot definir com la classe de problemes de decisió que resolt una màquina de Turing no determinista i que:

* si el nombre de camins és senar, la resposta es SI
* si el nombre de camins és parell, la resposta es NO

La classe ⊕P és una classe comptadora, i es pot veure com trobar el bit menys significatiu de la resposta del problema corresponent a la classe #P. El problema de trobar el bit més significatiu és a la classe PP.
Q5157286
teoria de la complexitat
Concept
Q908207
classe de complexitat
Concept
Q3262192
problemes de decisió
Concept
Q1190223
màquina de Turing no determinista
Concept
Q1063380
classe #P
MEDIA
Q1563053
classe PP
MISC
Q7137529
⊕P
MISC
Q7137529
⊕P
MISC
instance of
has quality