Проблема с определением p

Question

В "Введение в алгоритмы: 3 -е издание" есть теорема 34.2, в которой говорится

$ P = {l mid l text {принимается алгоритмом полиномиального времени} } $

"Принято в полиномиальное время" определяется:

$ L $ принимается в полиномиальное время алгоритмом $ a $, если он принимается на $ a $, и если, кроме того, существует постоянная $ k $, так что для любой строки длиной n x in l $, алгоритм $ $ Принимает $ x $ во времени $ O (n^k) $.

"Принято" определяется:

Язык, принятый алгоритмом $ a $, является набором строк $ l = {x in {0,1 }^* mid a (x) = 1 } $, то есть набор строк что алгоритм принимает.

Но что, если мы возьмем $ k = 0 $, и алгоритм $ a ( cdot) = 1 $, что просто возвращает 1 для всего? Разве это не значит, что $ p $ - это просто класс всех языков?

Answer 1

Нет, это означает, что язык $ l $, который содержит все возможные слова ($ l = sigma^*$), находится в $ p $. Другими словами, независимо от того, каков ваш вклад, алгоритм принимает. И соответствующий язык, конечно, (тривиально) решающего в полиномиальное время.

Чтобы уточнить вещи: язык-это набор слов (слова считаются кодировками да-младших задач). Класс сложности - это набор языков - так что это набор наборов. Когда язык $ l $ содержит все возможные слова, это не означает, что класс сложности, который содержит $ l $, содержит все языки.