Problema con la definición de P

Question

"Introducción a los algoritmos: 3rd Edition" no es el teorema 34.2, que establece

$ P = \ {L \ mediados L \ text {es aceptado por un algoritmo de tiempo polinomial} \} $

"Aceptada en tiempo polinómico" se define por:

$ L $ se acepta en el tiempo polinomio por un algoritmo $ A $ si es aceptada por $ A $ y si además existe una constante k $ $ de tal manera que para cualquier longitud-n string $ x \ in L $, algoritmo $ A $ acepta $ x $ en el tiempo $ O (n ^ k) $.

"Aceptada" se define por:

La lengua aceptada por un algoritmo $ A $ es el conjunto de cadenas $ L = \ {x \ in \ {0,1 \} ^ * \ mediados A (x) = 1 \} $, es decir, el conjunto de cadenas que el algoritmo acepta.

Pero lo que si tomamos k = $ 0 $, y el algoritmo de $ A (\ cdot) = 1 $, que sólo devuelve 1 para todo? ¿No significa eso, que $ P $ es sólo la clase de todas las lenguas?

Answer 1

No significa esto, que el lenguaje $ L $ que contiene todas las palabras posibles ($ L = \ Sigma ^ * $) está en $ P $. En otras palabras, no importa cuál es su entrada, el algoritmo acepta. Y el idioma correspondiente es, por supuesto, decidible (trivial) en tiempo polinómico.

Para aclarar las cosas: Una lengua es un conjunto de palabras (las palabras son consideradas como las codificaciones de los sí-instancias de un problema). Una clase de complejidad es un conjunto de idiomas - lo que es un conjunto de conjuntos. Cuando una lengua $ L $ contiene todas las palabras posibles, que no quiere decir que una clase de complejidad que contiene $ L $, contiene todos los idiomas.