P und NP als Wortproblem
Es sei A ein Algorithmus und die Eingabe von A ein Element (Wort) aus ?* für ein Alphabet ?.
Für jedes Eingabewort w? ?* sei
s(w) = Anzahl der Schritte bis zur Terminierung
sA(n) = maximale Schrittzahl, wobei
sA(n) = max {s(w)| mit w ? ?* , |w| =n}