P的定义问题

Question

在 “算法简介：第三版” 有定理34.2，它指出

$ p = {l mid l text {被多项式时算法} } $接受

“以多项式时间接受” 由：

$ l $在多项式时间内被算法$ a $接受，如果它被$ a $接受，并且此外还有一个常数$ k $，以便对于任何长度为n string $ x in L $，算法$， a $接受$ x $在时间$ o（n^k）$。

“公认” 由：

算法$ a $接受的语言是一组字符串$ l = {x in {0,1 }^* mid a（x）= 1 } $，即该算法接受。

但是，如果我们服用$ k = 0 $，而算法$ a（ cdot）= 1 $，那只是返回所有内容的1 $怎么办？这是否意味着，$ p $只是所有语言的班级吗？

Answer 1

不，这意味着包含所有可能单词（$ l = sigma^*$）的语言$ l $在$ p $中。换句话说，无论您的输入是什么，算法都接受。当然，相应的语言在多项式时间内（琐碎）可决定。

要澄清事物：语言是一组单词（这些单词被认为是问题是问题的编码）。复杂性类是一组语言 - 因此它是一组集。当语言$ l $包含所有可能的单词时，并不意味着包含$ l $的复杂性类包含所有语言。