Frage: Eigenschaften Polynomialzeit-Sprachen?
B ∈ ∑* und B ∈ P, wobei gilt, eine Sprache L ist in Klasse P, falls ihr Wortproblem von einer deterministischen Turing-Maschine mit polynomialer Laufzeit O(n^k) mit k ≥ 0 gelöst werden kann, dann gilt
das Inputwort w ist in O(m^l) Schritten zu lösen, wobei m die Wortlänge des Inputwortes ist.
Wie kann man das beweisen?