PTIME

Die Klasse PTIME (oder P) enthält alle Probleme,
die durch einen Algorithmus gelöst werden können,
dessen Laufzeit auf Eingaben der Länge $n$ durch ein Polynom $p(n)$ beschränkt ist.

Formal:
PTIME ist die Menge aller Sprachen,
die von einer deterministischen Turingmaschine
in Zeit $p(n)$ für ein Polynom $p$ entschieden werden können.

Beispiele:

• Berechnung maximaler Flüsse in Netzwerken
• 2-Färbbarkeit
• Auswertungsproblem der Aussagenlogik