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.

  1. ↑ Gill, Computational Complexity of Probabilistic Turing Machines, SIAM Journal on Computing, Band 6, 1977, S. 675–695.
Dieser Artikel wurde von Wikipedia herausgegeben. Der Text ist unter Creative Commons Attribution-Share Alike 4.0 verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.