Probabilistische Polynomialzeit

In der Komplexitätstheorie ist PP die Klasse der Entscheidungen, die von einer probabilistischen Turingmaschine in Polynomialzeit gelöst werden können. Die Antwort soll dabei in mindestens der Hälfte der Fälle richtig sein. Die Abkürzung PP steht für Probabilistische Polynomialzeit.

PP wurde durch John T. Gill eingeführt.<ref>Gill, Computational Complexity of Probabilistic Turing Machines, SIAM Journal on Computing, Band 6, 1977, S. 675–695.</ref>

Eigenschaften

PP ist abgeschlossen unter Komplementbildung,<ref name="BoCr195" /> Vereinigung und Schnitt.<ref name="BRS91" /> Das bedeutet, dass für zwei Sprachen <math>L_1, L_2 \in \mathcal{PP}</math> auch <math>L_1^c, L_1 \cup L_2, L_1 \cap L_2 \in \mathcal{PP}</math>. 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.<ref name="BoCr199" />

Beziehung zu anderen Komplexitätsklassen

PP enthält BQP<ref name="ADH97" /> und damit auch BPP. PP enthält auch NP <math>\cup</math> co-NP und ist selbst enthalten in PSPACE.<ref name="BoCr195" />

Einzelnachweise

<references> <ref name="ADH97">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]). </ref> <ref name="BRS91">Richard Beigel, Nick Reingold, Daniel Spielman: PP is closed under intersection. In: STOC '91. ACM, 1991, S. 1–9, doi:10.1145/103418.103426. </ref> <ref name="BoCr195">Daniel Pierre Bovet und Pierluigi Crescenzi: Introduction to the Theory of Complexity. Prentice Hall, 1994, ISBN 0-13-915380-2, S. 195. </ref> <ref name="BoCr199">Daniel Pierre Bovet und Pierluigi Crescenzi: Introduction to the Theory of Complexity. Prentice Hall, 1994, ISBN 0-13-915380-2, S. 199. </ref> </references>

Weblinks

PP. In: Complexity Zoo. (englisch)