imported>Turtoise16: Der Satz war meiner Meinung nach grammatikalisch falsch und nicht verständlich. Ich habe inhaltlich versucht, so zu lassen, wie er war, aber verständlich zu formulieren. Falls er jetzt inhaltlich falsch ist, dann war er es vermutlich schon vorher.

2026-01-21T09:46:38Z

Der Satz war meiner Meinung nach grammatikalisch falsch und nicht verständlich. Ich habe inhaltlich versucht, so zu lassen, wie er war, aber verständlich zu formulieren. Falls er jetzt inhaltlich falsch ist, dann war er es vermutlich schon vorher.

Neue Seite

In der [[Komplexitätstheorie]] ist '''PP''' die Klasse der Entscheidungen, die von einer [[Probabilistische Turingmaschine|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 [[Abgeschlossenheit (algebraische Struktur)|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 [[Aussagenlogik|aussagenlogische]] [[logische Formel|Formel]] von mehr als der Hälfte aller möglichen [[Belegung (Logik)|Belegungen]] [[Erfüllbarkeit|erfüllt]] wird.<ref name="BoCr199" />

== Beziehung zu anderen Komplexitätsklassen ==

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

== Einzelnachweise ==
<references>
<ref name="ADH97">{{Literatur
| Autor=Leonard M. Adleman, Jonathan DeMarrais, Ming-Deh A. Huang
| Titel=Quantum Computability
| Sammelwerk=SIAM Journal on Computing
| Band=26
| Nummer=5
| Verlag=[[SIAM]]
| Jahr=1997
| Seiten=1524-1540
| Online=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.205.8140&rep=rep1&type=pdf
| Format =PDF
}}</ref>
<ref name="BRS91">{{Literatur
| Autor=Richard Beigel, Nick Reingold, Daniel Spielman
| Titel=PP is closed under intersection
| Sammelwerk=STOC '91
| Verlag=ACM
| Jahr=1991
| Seiten=1-9
| DOI=10.1145/103418.103426
}}</ref>
<ref name="BoCr195">{{Literatur
| Autor=Daniel Pierre Bovet und Pierluigi Crescenzi
| Titel=Introduction to the Theory of Complexity
| Verlag=Prentice Hall
| Jahr=1994
| Seiten=195
| ISBN=0-13-915380-2
}}</ref>
<ref name="BoCr199">{{Literatur
| Autor=Daniel Pierre Bovet und Pierluigi Crescenzi
| Titel=Introduction to the Theory of Complexity
| Verlag=Prentice Hall
| Jahr=1994
| Seiten=199
| ISBN=0-13-915380-2
}}</ref>
</references>

== Weblinks ==
* {{Complexity Zoo|PP|P#pp}}

[[Kategorie:Komplexitätsklasse]]

Probabilistische Polynomialzeit - Versionsgeschichte

imported>Turtoise16: Der Satz war meiner Meinung nach grammatikalisch falsch und nicht verständlich. Ich habe inhaltlich versucht, so zu lassen, wie er war, aber verständlich zu formulieren. Falls er jetzt inhaltlich falsch ist, dann war er es vermutlich schon vorher.