Problème avec la définition de P

Question

"Introduction aux algorithmes: 3ème édition" il est le théorème 34.2, qui stipule

  

$ P = \ {L \ mi L \ texte {est acceptée par un algorithme polynomial} \} $

"Acceptée en temps polynomiale" est définie par:

  

$ L $ est acceptée en temps polynomial par un algorithme $ A $ si elle est acceptée par $ A $       et si en plus il existe un k $ constant $ tel que pour toute chaîne de longueur n $ x \ in L $,       algorithme $ A $ accepte $ x $ dans le temps $ O (n ^ k) $.

"accepté" est définie par:

  

La langue acceptée par un algorithme $ A $ est l'ensemble des chaînes           $ L = \ {x \ in \ {0,1 \} ^ * \ mid A (x) = 1 \} $,       qui est, l'ensemble des chaînes que l'algorithme accepte.

Mais si l'on prend $ k = 0 $ et algorithme $ A (\ cdot) = 1 $, ce qui revient à seulement 1 pour tout? Ne serait-ce que cela signifie que $ P $ est classe juste de toutes les langues?

Answer 1

Pas ce moyen, que la langue $ L $ qui contient tous les mots possibles ($ L = \ Sigma ^ * $) est en $ P $. En d'autres termes, peu importe ce que votre entrée est, l'algorithme accepte. Et la langue correspondant est bien sûr (trivialement) décidable en temps polynomial.

Pour clarifier les choses: la langue A est un ensemble de mots (les mots sont considérés comme codages des oui-instances d'un problème). Une classe de complexité est un ensemble de langues - il est donc un ensemble d'ensembles. Quand une langue $ L $ contient tous les mots possibles, cela ne signifie pas qu'une classe de complexité qui contient $ L $, contient toutes les langues.