0 Daumen
310 Aufrufe

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?


Avatar von
B ∈ ∑* und B ∈  P

Welche Relevanz hat B für deine Frage? B taucht im folgenden nicht mehr auf.

Außerdem scheint B laut B ∈ ∑* ein Wort zu sein und laut B ∈ P eine Sprache zu sein.

das Inputwort w ist in O(ml) Schritten zu lösen

Wo kommt das Wort w her?

Wo kommt der Exponent l her?

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community