計算理論・ラムダ計算の問題
言語はすべてアルファベット 上の言語（ の部分集合）とする。言語 に対し、 は多項式時間多対一帰着（カープ帰着）が存在すること、すなわち多項式時間で計算できる関数 で、すべての について となるものが存在することを表す。NP 完全性はこの に関して定める（ に属し、 のすべての言語が で帰着されること）。また 、 は非決定性対数領域で判定できる言語のクラス、 は決定性多項式領域で判定できる言語のクラスとし、 はチューリング機械の停止問題（決定不能である）を表す言語とする。
次のア〜キのうち、正しい（現在知られている結果から真であることが証明されている）ものをすべて選べ。
ア. 任意の言語 について、 かつ ならば である。
イ. 任意の言語 について、 かつ ならば である。
ウ. 任意の言語 について、 が NP 完全で、 かつ ならば、 は NP 完全である。
エ. である。
オ. 任意の言語 について、 ならば である。
カ. である。
キ. に属するすべての言語は NP 完全である。
この問題で使うもの
- 多項式時間多対一帰着の性質（説明と入口の問題）
- 計算量クラスの包含関係と完全問題（説明と入口の問題）
- 停止問題と決定可能性（説明と入口の問題）
この問題を解けるようになるまで（24 技能）
読み込み中…
右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
ヒント
行き詰まったら、上から順に 1 つずつ開いてください。
ヒント 1
帰着 は「 が易しければ も易しい」という向きの情報しか与えません。各命題について、証明できるか、決定不能な言語や空集合などを使った反例が作れるかを考えましょう。
ヒント 2
多項式時間関数の合成は多項式時間です（ の推移性）。クラスの真の包含には、時間階層定理・領域階層定理・サヴィッチの定理が使えます。
ヒント 3
イ・オは 、 を試してみましょう。キは に帰着できる言語が何かを考えます。
答えと解説
答えを見る
ア, ウ, エ, カ
どこでつまずきましたか？（選ぶと、戻る場所を案内します）
解説を読む
各選択肢を順に調べる。
ア（正しい） を多項式時間 で判定する機械 と、時間 で計算できる帰着 をとる。入力 に対し を計算し（）、 を 上で走らせれば、時間 で を判定できる。これは多項式なので 。
イ（誤り） 反例：、 とする。、 となる固定された列をとり、、 と定めると は多項式時間（定数時間）で計算でき、。 だが、 は決定不能なので （決定可能な言語のみからなる）に属さない。
ウ（正しい） 任意の について （ が NP 完全だから）かつ 。多項式時間関数の合成は多項式時間で計算できる（ なので の計算時間は ）から、 は推移的で 。これと より は NP 完全。
エ（正しい） 時間階層定理より がすべての について成り立つので、。よって 。
オ（誤り） イと同じ 、 では だが、もし なら、アと同じ議論で が決定可能になり矛盾する。
カ（正しい） サヴィッチの定理より 。領域階層定理より 。よって 。
キ（誤り） だが、 は NP 完全でない。実際、言語 が を満たすなら、すべての で なので 、すなわち である。 には空でない言語（例えば ）があるので、それは に帰着できない。この結論は と の関係によらない。
以上より、正しいものは ア, ウ, エ, カ である。
別解
各選択肢を検討する。
ア. 正しい。 を帰着関数とすると、。 の多項式時間判定機と の計算を合成すれば、 は の多項式で抑えられるので全体も多項式時間。よって 。
イ. 誤り。（決定不能）とし、 とする。 停止しない機械の符号（ の非要素）と定めれば だが 。向きが逆（ なら ）なら正しい。
ウ. 正しい。 であり、任意の は で、 は推移的（多項式時間関数の合成は多項式時間）なので 。
エ. 正しい。時間階層定理により であり、 と合わせて 。
オ. 誤り。、 とすると、 を への、... ではなく を の外へ送る必要があるが では不可。そこで , とすると で 。一方 なら を の要素に送る必要があり不可能。
カ. 正しい。Savitch の定理より 、領域階層定理より 。よって が証明されている。
キ. 誤り。 であるが、NP 完全言語（空でも でもない言語、たとえば SAT）から への帰着 は とならず存在しない。よって NP 完全ではない。
以上より正しいのは ア, ウ, エ, カ。