Klasse P

Die Klasse P enthält alle Entscheidungsprobleme, die von einer deterministischen Turingmaschine in Polynomzeit gelöst werden können:

Sie modelliert intuitiv „effizient lösbare Probleme“.