計算理論・ラムダ計算の問題

難易度 3大学院入試の専門科目の標準レベル大学院数学計算理論・ラムダ計算

$Σ = {0, 1}$ とし、言語とは $Σ^{*}$ （空列 $ε$ を含む $Σ$ 上の有限列全体）の部分集合のこととする。言語 $A, B$ について、 $A \leq_{p} B$ とは、多項式時間で計算できる全域関数 $f : Σ^{*} \to Σ^{*}$ であって、すべての $x \in Σ^{*}$ に対して $x \in A ⟺ f (x) \in B$ を満たすものが存在することとする。クラス $C$ に対して、言語 $A$ が $C$ 困難であるとは、すべての $L \in C$ について $L \leq_{p} A$ が成り立つことをいう。 $A$ が $C$ 困難であり、かつ $A \in C$ であるとき、 $A$ は $C$ 完全であるという。計算モデルは多テープの決定性・非決定性チューリング機械とし、 $P, NP, EXP = ⋃_{k \geq 1} DTIME (2^{n^{k}}), NL, PSPACE, NPSPACE$ は通常の意味の計算量クラスとする。また、停止問題を $HALT = {⟨ M, w ⟩ : 決定性チューリング機械 M は入力 w で停止する}$ とする。ここで $⟨ \cdot, \cdot ⟩$ は機械と入力の組の標準的な符号化（符号化と記述の相互変換が多項式時間でできるもの）であり、正しい符号化になっていない列は $HALT$ に属さないものとする。

次のア〜カのうち、（未解決問題の仮定なしに）正しいと証明されている主張をすべて選べ。

ア. $\emptyset$ でも $Σ^{*}$ でもない任意の言語 $A \in P$ は $P$ 完全である。

イ. 空集合 $\emptyset$ は $NP$ 困難である。

ウ. $HALT$ は $NP$ 困難である。

エ. $PSPACE ⊊ NPSPACE$ である。

オ. $EXP$ 完全な言語であって $P$ に属するものが存在する。

カ. $NL ⊊ PSPACE$ である。

この問題で使うもの

多項式時間多対一帰着の性質（説明と入口の問題）
停止問題と決定可能性（説明と入口の問題）
計算量クラスの包含関係と完全問題（説明と入口の問題）

この問題を解けるようになるまで（24 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

各主張が「定義から直接わかること」か「階層定理・サヴィッチの定理から従うこと」かを見分けよう。 $P$ 対 $NP$ のような未解決問題に依存する主張は含まれていない。

ヒント 2

帰着 $A \leq_{p} B$ では、 $B$ が空集合だと「属する」側の行き先がなくなる。一方 $B$ 自体が $P$ に属し自明でなければ「先に答えを計算して代表元に写す」帰着が作れる。また時間階層定理から $P \neq = EXP$ 、サヴィッチの定理から $NSPACE (s) \subseteq SPACE (s^{2})$ が従う。

ヒント 3

NP の言語 $L$ から HALT への帰着は「 $x$ を内蔵し、長さ $p (∣ x ∣)$ 以下の計算経路をすべて調べ、受理経路があれば停止、なければ無限ループする機械」を出力すればよい。 $NL$ については $NL \subseteq SPACE (lo g^{2} n)$ と空間階層定理を組み合わせる。

答えと解説

答えを見る

ア, ウ, カ

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

各主張を順に調べる。

ア（正しい） $A \in P$ で $A \neq = \emptyset, A \neq = Σ^{*}$ とし、 $a \in A$ , $b \in / A$ を 1 つずつ固定する。任意の $B \in P$ に対して
$f (x) = {a b (x \in B) (x \in / B)$
と定める。 $B$ の判定は多項式時間ででき、 $a, b$ は入力によらない定数なので、 $f$ は多項式時間計算可能な全域関数であり、 $x \in B ⟺ f (x) \in A$ が成り立つ。よって $B \leq_{p} A$ である。 $A \in P$ と合わせて $A$ は $P$ 完全である。

イ（誤り） $Σ^{*} \in P \subseteq NP$ である。もし $Σ^{*} \leq_{p} \emptyset$ を与える $f$ があれば、 $ε \in Σ^{*}$ に対し $f (ε) \in \emptyset$ とならなければならず矛盾する。したがって $\emptyset$ は $NP$ 困難でない（未解決問題とは無関係に偽）。

ウ（正しい） $L \in NP$ を、時間 $p (n)$ （ $p$ は多項式）で動く非決定性チューリング機械 $N$ が判定するとする。入力 $x$ に対し、次の決定性機械 $M_{x}$ を作る：「 $x$ を内蔵し、空の入力から始めて、 $N$ の $x$ 上の長さ $p (∣ x ∣)$ 以下の計算経路をすべて順に模倣する。受理する経路が見つかれば停止し、見つからなければ無限ループに入る」。 $M_{x}$ の記述は、 $N$ の記述（ $x$ によらない定数）と $x$ と $p (∣ x ∣)$ の値を埋め込むだけで書き出せるので長さも計算時間も $∣ x ∣$ の多項式で抑えられ、 $f (x) = ⟨ M_{x}, ε ⟩$ は多項式時間計算可能である。そして
$x \in L ⟺ N が x を受理する ⟺ M_{x} が停止する ⟺ f (x) \in HALT .$
よって $L \leq_{p} HALT$ であり、 $HALT$ は $NP$ 困難である（なお $HALT$ は決定不能なので $NP$ には属さず、 $NP$ 完全ではない）。

エ（誤り） サヴィッチの定理より $s (n) \geq lo g n$ のとき $NSPACE (s (n)) \subseteq SPACE (s (n)^{2})$ であり、多項式の 2 乗は多項式なので $NPSPACE \subseteq PSPACE$ 。逆の包含は決定性機械が非決定性機械の特別な場合であることから明らかなので $PSPACE = NPSPACE$ であり、真の包含ではない。

オ（誤り） $A$ が $EXP$ 完全で $A \in P$ と仮定する。任意の $L \in EXP$ について $L \leq_{p} A$ であり、 $P$ は $\leq_{p}$ について下に閉じている（ $f (x)$ を計算してから $A$ を判定すればよく、 $∣ f (x) ∣$ は $∣ x ∣$ の多項式で抑えられ、多項式の合成は多項式）ので $L \in P$ 。よって $EXP \subseteq P$ 。一方、時間階層定理より
$P \subseteq DTIME (2^{n}) ⊊ DTIME (2^{n^{2}}) \subseteq EXP$
なので $P \neq = EXP$ であり矛盾する。したがってそのような言語は存在しない。

カ（正しい） サヴィッチの定理より $NL \subseteq SPACE (lo g^{2} n)$ 。 $lo g^{2} n = o (n)$ であり $n$ は空間構成可能なので、空間階層定理より $SPACE (lo g^{2} n) ⊊ SPACE (n) \subseteq PSPACE$ 。よって $NL ⊊ PSPACE$ 。

以上より、正しいのはア, ウ, カである。

別解

ア: 正しい。 $A \in P$ で $\emptyset, Σ^{*}$ でないので、 $a \in A$ と $b \in / A$ を固定できる。任意の $L \in P$ に対し、 $f (x) = a$ （ $x \in L$ のとき）、 $f (x) = b$ （ $x \in / L$ のとき）と定めると、 $f$ は多項式時間で計算でき、 $x \in L ⟺ f (x) \in A$ となる。したがって $A$ は $P$ 困難であり、 $A \in P$ なので $P$ 完全である。

イ: 誤り。 $L \leq_{p} \emptyset$ ならば、すべての $x$ で $f (x) \in / \emptyset$ なので $L = \emptyset$ となる。 $NP$ には $Σ^{*}$ のような空でない言語があるので、 $\emptyset$ は $NP$ 困難ではない。

ウ: 正しい。 $L \in NP$ に対し、 $L$ を決定する指数時間の決定性機械 $M_{L}$ を作る。 $M_{L}$ は $x \in L$ なら停止し、 $x \in / L$ なら無限ループに入るものとする。このとき $x \mapsto ⟨ M_{L}, x ⟩$ は多項式時間で計算でき、 $x \in L ⟺ ⟨ M_{L}, x ⟩ \in HALT$ となる。よって $HALT$ は $NP$ 困難である。

エ: 誤り。Savitch の定理より $PSPACE = NPSPACE$ である。

オ: 誤り。 $P$ に属する $EXP$ 完全な言語が存在すれば、 $EXP \subseteq P$ となる。これは時間階層定理（ $P ⊊ EXP$ ）に反する。

カ: 正しい。Savitch の定理より $NL \subseteq SPACE (lo g^{2} n)$ である。空間階層定理より $SPACE (lo g^{2} n) ⊊ SPACE (n) \subseteq PSPACE$ なので、 $NL ⊊ PSPACE$ である。

以上より、正しいのはア、ウ、カ。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる