pの定義に関する問題

Question

の 「アルゴリズムの紹介：第3版」 定理34.2があります

$ p = {l mid l text {は、多項式時間アルゴリズム} } $によって受け入れられます。

「多項式時間に受け入れられた」 定義されています：

$ l $は、アルゴリズムによって多項式時間に受け入れられます$ a $は$ a $で受け入れられ、さらに$ k $が存在する場合は、任意の長さのstring $ x in l $、algorithm $の場合$は$ x $ in time $ o（n^k）$を受け入れます。

「受け入れられた」 定義されています：

アルゴリズム$ a $によって受け入れられる言語は、文字列$ l = {x in {0,1 }^* mid a（x）= 1 } $のセットです。アルゴリズムが受け入れること。

しかし、$ k = 0 $を取得し、アルゴリズム$ a（ cdot）= 1 $を取得した場合はどうなりますか？それは、$ p $がすべての言語のクラスにすぎないという意味ではないでしょうか？

Answer 1

いいえ、これは、すべての可能な単語（$ l = sigma^*$）を含む言語$ l $が$ p $にあることを意味します。言い換えれば、あなたの入力が何であれ、アルゴリズムは受け入れます。そして、もちろん、対応する言語は、多項式時間で（些細な）決定可能です。

物事を明確にするために：言語は一連の単語です（単語は問題のYESインスタンスのエンコーディングと見なされます）。複雑なクラスは一連の言語です。したがって、セットのセットです。言語$ l $に考えられるすべての単語が含まれている場合、$ l $を含む複雑さのクラスにすべての言語が含まれていることを意味するものではありません。