⊕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.[1]
També es pot definir com la classe de problemes de decisió que resolt una màquina de Turing no determinista i que:[2]
- 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.
Relació amb d'altres classes
[modifica]Pel teorema de Toda se sap que PPP conté la classe PH, però no se sap si P⊕P si conté NP. Però la primera part del teorema mostra que BPP⊕P conté a PH.[3]
El problema d'isomorfisme de grafs està dins de la classe ⊕P.
Referències
[modifica]- ↑ Papadimitriou, Christos H.; Zachos, Stathis K. Two remarks on the power of counting. Berlin/Heidelberg: Springer-Verlag, p. 269–275. DOI 10.1007/bfb0036487. ISBN 3540119736.
- ↑ «Complexity Zoo:Symbols - Complexity Zoo» (en anglès). Arxivat de l'original el 2018-01-19. [Consulta: 3 desembre 2018].
- ↑ Fortnow, Lance «A Simple Proof of Toda's Theorem» (en anglès). Theory of Computing, 5, 1, 2009, pàg. 135–140. DOI: 10.4086/toc.2009.v005a007. ISSN: 1557-2862.
| Considerades tractables | |
|---|---|
| Suposadament intractables | UP · NP · NP-complet · NP-hard · co-NP · co-NP-complet · AM · QMA · PH · ⊕P · PP · ♯P · ♯P-complet · IP · PSPACE · PSPACE-complet |
| Considerades intractables | |
| Jerarquia de classes | |
| Families de classes | |
