Definition:
Eine Menge, Sprache oder ein Problem L heißt polynomial-zeitbeschränkt, wenn die charakteristische Funktion CL polynomial-zeitberechenbar ist.
P = { L ? ?* : L polynomial-zeitbeschränkt }
heißt die Klasse der pzb-Sprachen.
NP = { L ? ?* : L nichtdeterministisch
polynomial-zeitbeschränkt }
heißt die Klasse der npzb- Sprachen.
P = { f: ?* ? ?* und f polynomial-zeitberechenbar }
heißt die Klasse der pzb-Funktionen