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

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

アルファベットを $Σ = {0, 1}$ とし、言語とは $Σ^{*}$ の部分集合のこととする。言語 $A, B$ について、多項式時間で計算できる関数 $f : Σ^{*} \to Σ^{*}$ で、すべての $x \in Σ^{*}$ に対して $x \in A ⟺ f (x) \in B$ をみたすものが存在するとき $A \leq_{p} B$ と書く（多項式時間多対一帰着）。NP 完全性はこの $\leq_{p}$ に関するものとする。また、 $SAT$ は CNF 論理式の充足可能性問題、 $HALT = {⟨ M, x ⟩ ∣ チューリング機械 M は入力 x で停止する}$ は停止問題（ $Σ$ 上の適当な符号化によるもの）とする。

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

ア. $A \leq_{p} B$ かつ $B \in NP$ ならば $A \in NP$ である。

イ. $A \leq_{p} B$ かつ $A \in P$ ならば $B \in P$ である。

ウ. $P ⊊ EXP$ である。

エ. $HALT \leq_{p} SAT$ である。

オ. ある NP 完全な言語 $L$ が $coNP$ に属するならば、 $NP = coNP$ である。

カ. $A \in P$ であり、 $B$ が $B \neq = \emptyset$ かつ $B \neq = Σ^{*}$ をみたす任意の言語（決定可能でなくてもよい）ならば、 $A \leq_{p} B$ である。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

それぞれの命題について、定義から直接示せるか、反例が作れるか、既知の定理（時間階層定理、停止問題の決定不能性）に帰着できるかを考えよう。

ヒント 2

帰着 $A \leq_{p} B$ は「 $B$ が簡単なら $A$ も簡単」を伝えるが、逆向きの情報は伝えない。また、 $A \leq_{p} B$ なら補集合についても $A \leq_{p} B$ が同じ $f$ で成り立つ。

ヒント 3

イとカでは、 $B$ の元 $y_{1}$ と $B$ に属さない元 $y_{0}$ を 1 つずつ固定し、 $x$ に応じてどちらかを出力する関数を考えるとよい。エでは $SAT$ が決定可能であることに注目する。

答えと解説

答えを見る

ア, ウ, オ, カ

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

解説を読む

各命題を順に調べる。

ア（正しい） $B \in NP$ なので、多項式時間の検証機 $V$ と多項式 $q$ があって $y \in B ⟺ \exists w (∣ w ∣ \leq q (∣ y ∣), V (y, w) = 1)$ となる。帰着 $f$ の計算時間を多項式 $p$ で抑えると $∣ f (x) ∣ \leq p (∣ x ∣)$ である。そこで $x$ に対して $f (x)$ を計算し、長さ $q (p (∣ x ∣))$ 以下の証拠 $w$ で $V (f (x), w)$ を検証すれば、これは $A$ の多項式時間検証になる。よって $A \in NP$ 。

イ（誤り） 反例を作る。 $A = {0} \in P$ 、 $B = HALT$ とする。 $HALT$ は空でなく、補集合も空でないので、 $y_{1} \in HALT$ と $y_{0} \in / HALT$ を 1 つずつ固定できる。 $f (x) = y_{1} (x = 0), f (x) = y_{0} (x \neq = 0)$ は多項式時間で計算でき、 $x \in A ⟺ f (x) \in B$ をみたす。よって $A \leq_{p} B$ だが、 $HALT$ は決定不能なので $B \in / P$ 。

ウ（正しい） 時間階層定理により $DTIME (n^{k}) ⊊ DTIME (2^{n})$ がすべての $k$ で成り立つ（より強く、 $P \subseteq DTIME (2^{n}) ⊊ DTIME (2^{n^{2}}) \subseteq EXP$ ）。したがって $P ⊊ EXP$ は証明されている。

エ（誤り） $SAT$ は決定可能（全割り当てを試せばよい）である。もし $HALT \leq_{p} SAT$ なら、 $f (x)$ を計算してから $SAT$ を判定することで $HALT$ が決定可能になり、停止問題の決定不能性に矛盾する。

オ（正しい） 任意の $A \in NP$ に対し、 $L$ が NP 完全なので $A \leq_{p} L$ 。同じ $f$ について $x \in A ⟺ f (x) \in L$ だから $A \leq_{p} L$ 。仮定 $L \in coNP$ より $L \in NP$ なので、アより $A \in NP$ 、すなわち $A \in coNP$ 。よって $NP \subseteq coNP$ 。この両辺の補を取ると $coNP \subseteq NP$ も得られ、 $NP = coNP$ 。

カ（正しい） $y_{1} \in B$ 、 $y_{0} \in / B$ を固定する。 $f (x)$ を「 $x \in A$ を多項式時間で判定し、 $x \in A$ なら $y_{1}$ 、そうでなければ $y_{0}$ を出力する」と定めれば、 $f$ は多項式時間で計算でき（ $y_{0}, y_{1}$ は定数）、 $x \in A ⟺ f (x) \in B$ をみたす。 $B$ の判定はまったく必要ないので、 $B$ が決定不能でもよい。

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

別解

各選択肢を検討する。

ア. 正しい。 $f$ を $A \leq_{p} B$ の帰着とすると、 $x \in A ⟺ f (x) \in B$ 。 $B \in NP$ の検証機を使い、 $x$ に対して $f (x)$ を多項式時間で計算し（ $∣ f (x) ∣$ は $∣ x ∣$ の多項式で抑えられる）、 $B$ の検証機に $f (x)$ と証拠を渡せば $A$ の検証機が得られる。よって $A \in NP$ 。

イ. 誤り。 $A \in P$ でも $B$ は難しくてよい。例えば $A = \emptyset$ 、 $B = HALT$ とすると、 $f (x) =$ （ $HALT$ に属さない固定の語）で $A \leq_{p} B$ かつ $A \in P$ だが $B \in / P$ （決定不能）。帰着は「 $B$ が易しければ $A$ が易しい」方向にのみ働く。

ウ. 正しい。時間階層定理により $DTIME (2^{n}) ⊋ DTIME (n^{k})$ の意味で、 $P \subseteq DTIME (2^{n}) \subseteq EXP$ かつ $DTIME (2^{n})$ には $P$ に属さない言語が存在する（ $DTIME (2^{n}) \neq \subseteq DTIME (2^{n /2}) \supseteq P$ ）。よって $P ⊊ EXP$ は無条件に証明されている。

エ. 誤り。 $SAT$ は決定可能（全割当を試せばよい）。 $HALT \leq_{p} SAT$ なら（ $f$ は計算可能なので） $HALT$ も決定可能になり、停止問題の決定不能性に反する。

オ. 正しい。 $L$ を NP 完全かつ $L \in coNP$ とする。任意の $A \in NP$ について $A \leq_{p} L$ 、よって補言語について $A \leq_{p} L$ 。 $L \in coNP$ より $L \in NP$ 、アと同様に $A \in NP$ 、すなわち $A \in coNP$ 。よって $NP \subseteq coNP$ 。補集合を取れば $coNP \subseteq NP$ 。ゆえに $NP = coNP$ 。

カ. 正しい。 $b_{1} \in B$ 、 $b_{0} \in / B$ を固定（ $B \neq = \emptyset, Σ^{*}$ より存在）。 $f (x) = b_{1}$ ( $x \in A$ )、 $f (x) = b_{0}$ ( $x \in / A$ ) と定めると、 $A \in P$ より $f$ は多項式時間で計算でき、 $x \in A ⟺ f (x) \in B$ 。

以上より、正しいと証明されているのはア, ウ, オ, カ。

この問題の確認

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

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

確認の方法について

間違いを報告する

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