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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.