Attention
NPTime, kurz NP, der Probleme, die von einer nichtdeterministischen Turing Maschine in Polynomialzeit gelöst werden können.
Satz
Also
Ein Problem L liegt in NP genau dann, wenn Lösungen für L in Polynomialzeit verifiziert werden können.
Beweis
