Probabilistische Polynomialzeit
From Wikipedia, the free encyclopedia
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.[1]
Eigenschaften
PP ist abgeschlossen unter Komplementbildung,[2] Vereinigung und Schnitt.[3] Das bedeutet, dass für zwei Sprachen auch . 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]
