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

難易度 2大学院の講義の演習問題レベル大学院数学計算理論・ラムダ計算

$Σ = {0, 1}$ とし、言語とは $Σ^{*}$ の部分集合のこととする。言語 $A, B$ に対し、 $A \leq_{p} B$ は $A$ が $B$ に多項式時間多対一帰着（カープ帰着）可能であること、すなわち多項式時間で計算できる全域関数 $f : Σ^{*} \to Σ^{*}$ で、すべての $x \in Σ^{*}$ について $x \in A ⟺ f (x) \in B$ となるものが存在することを表す。 $NP$ 完全性はこの $\leq_{p}$ に関するものとする。 $L$ , $P$ , $NP$ , $PSPACE$ , $NPSPACE$ は標準的な計算量クラスとする。

次の主張のうち、（未解決問題の答えによらず）正しいと証明されているものをすべて選べ。

ア　すべての言語 $A, B$ について、 $A \leq_{p} B$ かつ $B \in P$ ならば $A \in P$ である。
イ　すべての言語 $A, B$ について、 $A \leq_{p} B$ かつ $A \in P$ ならば $B \in P$ である。
ウ　すべての言語 $A, B$ について、 $A$ が $NP$ 完全で、 $B \in NP$ かつ $A \leq_{p} B$ ならば、 $B$ は $NP$ 完全である。
エ　 $L = PSPACE$ である。
オ　 $NPSPACE = PSPACE$ である。
カ　すべての言語 $A, B$ について、 $A \leq_{p} B$ ならば $B \leq_{p} A$ である。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

帰着 $A \leq_{p} B$ は「 $A$ は $B$ より難しくない」ことを表す。どちら向きに計算量の情報が伝わるかを考えよう。決定不能な言語を使うと、誤りの主張の反例がつくれる。

ヒント 2

多項式時間関数の合成は多項式時間（ $\leq_{p}$ は推移的）。空間計算量については、空間階層定理とサヴィッチの定理 $NSPACE (s) \subseteq SPACE (s^{2})$ が使える。

ヒント 3

ア・ウは帰着の合成で示せる。イ・カは $A = {0}$ と停止問題で反例がつくれる。残りのエ・オは階層定理とサヴィッチの定理のどちらが当てはまるかを考えよう。

答えと解説

答えを見る

ア, ウ, オ

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

解説を読む

ア（正しい）： $f$ を $A \leq_{p} B$ を与える帰着とし、時間 $p (n)$ で計算できるとする。入力 $x$ （長さ $n$ ）に対し $f (x)$ を計算し、その長さは高々 $p (n)$ である。 $B$ を時間 $q (m)$ で判定する機械を $f (x)$ に走らせれば、全体の時間は $p (n) + q (p (n))$ で多項式である。 $x \in A ⟺ f (x) \in B$ なので $A \in P$ 。
イ（誤り）：反例として $A = {0} \in P$ 、 $B$ を停止問題（決定不能な言語）とする。 $B$ の元 $y_{1}$ と非元 $y_{0}$ を 1 つずつ固定し、 $f (x) = y_{1}$ （ $x = 0$ のとき）、 $f (x) = y_{0}$ （それ以外）と定めると、 $f$ は定数時間で計算でき $A \leq_{p} B$ となる。しかし $B$ は決定不能なので $B \in / P$ 。
ウ（正しい）：任意の $C \in NP$ について、 $A$ が $NP$ 困難なので $C \leq_{p} A$ 。 $\leq_{p}$ は推移的である（多項式時間関数の合成は多項式時間：長さ $p (n)$ 以下の出力に時間 $q$ の関数を適用しても $p (n) + q (p (n))$ で多項式）ので $C \leq_{p} B$ 。よって $B$ は $NP$ 困難で、 $B \in NP$ と合わせて $NP$ 完全である。
エ（誤り）： $L = SPACE (lo g n)$ である。空間階層定理より $SPACE (lo g n) ⊊ SPACE (n) \subseteq PSPACE$ なので、 $L \neq = PSPACE$ が証明されている。
オ（正しい）：サヴィッチの定理より、 $s (n) \geq lo g n$ に対し $NSPACE (s (n)) \subseteq SPACE (s (n)^{2})$ である。多項式の 2 乗は多項式なので $NPSPACE \subseteq PSPACE$ 。逆の包含は自明なので等しい。
カ（誤り）：イと同じ $A = {0}$ 、 $B$ ＝停止問題をとると $A \leq_{p} B$ である。もし $B \leq_{p} A$ なら、アの議論と同様に $B \in P$ となり、 $B$ が決定可能になって矛盾する。よって $B \neq \leq_{p} A$ 。

よって正しいものはア、ウ、オである。

別解

各選択肢を確かめる。
- ア: 正しい。 $f$ を帰着関数とすると、 $x \in A ⟺ f (x) \in B$ 。 $B \in P$ の判定アルゴリズムと $f$ の計算を合成すると、 $∣ f (x) ∣$ は $∣ x ∣$ の多項式なので全体も多項式時間。よって $A \in P$ 。
- イ: 誤り（証明できる反例がある）。 $A = \emptyset \in P$ 、 $B$ を決定不能な言語（たとえば停止問題）とし、 $f (x) =$ 固定した $B$ に属さない文字列 $w$ とすると、 $x \in A ⟺ f (x) \in B$ （両辺とも偽）なので $A \leq_{p} B$ だが $B \in / P$ 。
- ウ: 正しい。任意の $C \in NP$ について $C \leq_{p} A$ （ $A$ は NP 完全）、 $A \leq_{p} B$ で、 $\leq_{p}$ は推移的（帰着の合成は多項式時間）なので $C \leq_{p} B$ 。さらに $B \in NP$ だから $B$ は NP 完全。
- エ: 誤り。空間階層定理により $L ⊊ PSPACE$ （ $SPACE (lo g n) ⊊ SPACE (n)$ ）が証明されているので $L = PSPACE$ は偽。
- オ: 正しい。サヴィッチの定理 $NSPACE (s (n)) \subseteq SPACE (s (n)^{2})$ より $NPSPACE = PSPACE$ 。
- カ: 誤り。 $A = \emptyset$ 、 $B = {0}$ とすると $f (x) = ε$ で $A \leq_{p} B$ だが、 $B \leq_{p} A$ だと $0 \in B$ より $f (0) \in \emptyset$ となって矛盾するので不成立。

正しいと証明されているのはア、ウ、オ。

この問題の確認

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

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

確認の方法について

間違いを報告する

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