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.

Eigenschaften

PP ist abgeschlossen unter Komplementbildung,[1] Vereinigung und Schnitt.[2] Das bedeutet, dass für zwei Sprachen $L_{1},L_{2}\in {\mathcal {PP}}$ auch $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.[3]

Beziehung zu anderen Komplexitätsklassen

PP enthält BQP[4] und damit auch BPP. PP enthält auch NP $\cup$ co-NP und ist selbst enthalten in PSPACE.[1]

Einzelnachweise

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)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.

[BoCr195-1] Daniel Pierre Bovet und Pierluigi Crescenzi: Introduction to the Theory of Complexity. Prentice Hall, 1994, ISBN 0-13-915380-2, S. 195.

[BRS91-2] Richard Beigel, Nick Reingold, Daniel Spielman: PP is closed under intersection. In: STOC '91. ACM, 1991, S. 1–9, doi:10.1145/103418.103426.

[BoCr199-3] Daniel Pierre Bovet und Pierluigi Crescenzi: Introduction to the Theory of Complexity. Prentice Hall, 1994, ISBN 0-13-915380-2, S. 199.

[ADH97-4] 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]).