Problem mit der Definition von p

Question

Im "Einführung in Algorithmen: 3. Auflage" Es gibt Satz 34.2, der heißt

$ P = {l mid l text {wird von einem Polynom-Zeit-Algorithmus} } $ akzeptiert

"In Polynomzeit akzeptiert" wird definiert durch:

$ L $ wird in Polynomzeit von einem Algorithmus $ a $ akzeptiert, wenn es von $ a $ akzeptiert wird und wenn zusätzlich ein konstant $ k $ vorhanden ist, so dass für jede Länge-N-String $ x in L $ Algorithmus $ A $ akzeptiert $ x $ in Zeit $ o (n^k) $.

"Akzeptiert" wird definiert durch:

Die von einem Algorithmus $ a $ akzeptierte Sprache ist der Satz von Zeichenfolgen $ l = {x in {0,1 }^* Mid a (x) = 1 } $, dh der Satz von Strings dass der Algorithmus akzeptiert.

Aber was ist, wenn wir $ k = 0 $ und Algorithmus $ a ( cdot) = 1 $ nehmen, was nur 1 für alles zurückgibt? Würde das nicht bedeuten, dass $ p $ nur Klasse aller Sprachen ist?

Answer 1

Nein, dies bedeutet, dass die Sprache $ l $, die alle möglichen Wörter enthält ($ l = sigma^*$), in $ p $ ist. Mit anderen Worten, egal wie Ihre Eingabe ist, der Algorithmus akzeptiert. Und die entsprechende Sprache ist natürlich (trivial) in Polynomzeit lehnte.

Um Dinge zu klären: Eine Sprache ist eine Reihe von Wörtern (die Wörter werden als Codierungen der Ja-Instanzen eines Problems angesehen). Eine Komplexitätsklasse ist eine Reihe von Sprachen - also eine Reihe von Sets. Wenn eine Sprache $ l $ alle möglichen Wörter enthält, bedeutet dies nicht, dass eine Komplexitätsklasse, die $ l $ enthält, alle Sprachen enthält.