Problemi con la definizione di P

Question

"Introduzione agli algoritmi: 3rd Edition" non c'è Teorema 34.2, in cui si afferma

$ P = \ {L \ metà L \ text {è accettata da un algoritmo di tempo polinomiale} \} $

"Accettato in tempo polinomiale" è definita da:

$ L $ è accettata in tempo polinomiale da un algoritmo $ A $ se è accettato da $ A $ e se inoltre esiste una costante k $ $ tale che per qualsiasi lunghezza-n stringa $ x \ in L $, algoritmo di $ A $ accetta $ x $ in tempo $ O (n ^ k) $.

"Accettato" è definita da:

Il linguaggio accettato da un algoritmo di $ A $ è l'insieme di stringhe $ L = \ {x \ in \ {0,1 \} ^ * \ mid A (x) = 1 \} $, vale a dire l'insieme delle stringhe che l'algoritmo accetta.

Ma cosa succede se prendiamo $ k = 0 $, e l'algoritmo $ A (\ cdot) = 1 $, che restituisce solo 1 per tutto? Non sarebbe significa, che $ P $ è solo classe di tutte le lingue?

Answer 1

Non ci sono questo mezzo, che la lingua $ L $ che contiene tutte le parole possibili ($ L = \ Sigma ^ * $) è in $ P $. In altre parole, non importa quale sia il vostro ingresso è, l'algoritmo accetta. E la lingua corrispondente è ovviamente (banalmente) decidibile in tempo polinomiale.

Per chiarire le cose: Una lingua è un insieme di parole (le parole sono considerate come codifiche dei sì-istanze di un problema). Una classe di complessità è un insieme di lingue - quindi è un insieme di insiemi. Quando una lingua $ L $ contiene tutte le parole possibili, ciò non significa che una classe di complessità che contiene $ L $, contiene tutte le lingue.