Probabilistische Polynomialzeit
In der Komplexitätstheorie ist PP die Klasse der Entscheidungen, die in von einer probabilistischen Turingmaschine in Polynomialzeit lösbar ist und die Antwort in mindestens der Hälfte der Fälle richtig ist. Die Abkürzung PP steht für Probabilistische Polynomialzeit.
PP wurde durch John T. Gill eingeführt.[1]
Eigenschaften
PP ist abgeschlossen unter Komplementbildung,[2] Vereinigung und Schnitt.[3] Das bedeutet, dass für zwei Sprachen Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle L_{1},L_{2}\in {\mathcal {PP}}} auch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L_1^c, L_1 \cup L_2, L_1 \cap L_2 \in \mathcal{PP}} . Es ist also co-PP = PP.
Ein bekanntes PP-vollständiges Problem ist MAXSAT, das Entscheidungsproblem, ob eine aussagenlogische Formel von mehr als der Hälfte aller möglichen Belegungen erfüllt wird.[4]
Beziehung zu anderen Komplexitätsklassen
PP enthält BQP[5] und damit auch BPP. PP enthält auch NP Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \cup} co-NP und ist selbst enthalten in PSPACE.[2]
Einzelnachweise
- ↑ Gill, Computational Complexity of Probabilistic Turing Machines, SIAM Journal on Computing, Band 6, 1977, S. 675–695.
- ↑ a b Daniel Pierre Bovet und Pierluigi Crescenzi: Introduction to the Theory of Complexity. Prentice Hall, 1994, ISBN 0-13-915380-2, S. 195.
- ↑ Richard Beigel, Nick Reingold, Daniel Spielman: PP is closed under intersection. In: STOC '91. ACM, 1991, S. 1–9, doi:10.1145/103418.103426.
- ↑ Daniel Pierre Bovet und Pierluigi Crescenzi: Introduction to the Theory of Complexity. Prentice Hall, 1994, ISBN 0-13-915380-2, S. 199.
- ↑ Leonard M. Adleman, Jonathan DeMarrais, Ming-Deh A. Huang: Quantum Computability. In: SIAM Journal on Computing. Band 26, Nr. 5. SIAM, 1997, S. 1524–1540 (psu.edu [PDF]).
Weblinks
- PP. In: Complexity Zoo. (englisch)
