Menge aller Probleme, die mit Hilfe deterministischer Algorithmen in polynomialer Zeit gelöst werden können.

PTIME oder manchmal kurz P steht für die Klasse der Probleme mit Polynomialzeit-Algorithmen, also derjenigen Probleme, die wir bislang gut oder durchführbar genannt haben.

Klasse von Problemen, für welche Algorithmen existieren, deren maximal benötigte Anzahl Rechenschritte sich in Form eines Polynoms angeben lassen (deren Laufzeit also nicht exponentiell mit der Länge der Eingabedaten zunimmt). (Klasse der effizient lösbaren Probleme).