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

難易度 4大学院入試の難問レベル大学院数学計算理論・ラムダ計算

$Σ = {0, 1}$ とし、言語とは $Σ^{*}$ の部分集合のこととする。言語 $A, B$ について、 $A \leq_{p} B$ は $A$ が $B$ に多項式時間多対一帰着可能であること（多項式時間で計算できる全域関数 $f : Σ^{*} \to Σ^{*}$ で、すべての $x$ について $x \in A ⟺ f (x) \in B$ となるものが存在すること）を表す。言語 $B$ がクラス $C$ に対して困難であるとは、すべての $A \in C$ について $A \leq_{p} B$ となることをいい、困難かつ $B \in C$ のとき $C$ 完全という。 $HALT$ を、チューリング機械 $M$ と入力 $w$ の組の（標準的な）符号 $⟨ M, w ⟩$ のうち、 $M$ が $w$ 上で停止するもの全体からなる言語とする。 $SAT$ は充足可能な命題論理式（の符号）全体である。

次の命題のうち、正しいことが証明されているものをすべて選べ（ほかの命題はいずれも偽であることが証明されている）。

ア．任意の言語 $A, B$ について、 $A \leq_{p} B$ かつ $B \in NP$ ならば $A \in NP$ である。

イ．任意の言語 $A, B$ について、 $A \leq_{p} B$ かつ $A \in P$ ならば $B \in P$ である。

ウ． $L \in P$ が $L \neq = \emptyset$ かつ $L \neq = Σ^{*}$ を満たすならば、 $L$ は $\leq_{p}$ に関して $P$ 完全である。

エ．言語 $Σ^{*}$ は $NP$ 困難である。

オ． $NL ⊊ PSPACE$ である。

カ． $HALT$ は $NP$ 困難である。

キ． $\leq_{p}$ に関して $EXP$ 完全である言語のうち、 $P$ に属するものが存在する。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

各命題について、正しいなら帰着や階層定理で証明し、誤りなら $\emptyset$ , $Σ^{*}$ , $HALT$ のような極端な言語を使った反例を探しましょう。

ヒント 2

多対一帰着では、「属さない元」を「属さない元」に写す必要があります。 $Σ^{*}$ には属さない元がなく、 $\emptyset$ には属する元がないことに注意します。また、クラスの分離にはサヴィッチの定理と領域・時間階層定理が使えます。

ヒント 3

イは $A = \emptyset$ と決定不能な $B$ で反例が作れます。カは、NP の検証者で証拠を総当たりし、見つかったら停止する機械を $x$ ごとに作る帰着を考えます。キは「EXP 完全な言語が P にあれば EXP ⊆ P」となることを使います。

答えと解説

答えを見る

ア, ウ, オ, カ

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

解説を読む

ア（正しい）. $f$ を帰着関数、 $f$ の計算時間を多項式 $q$ で押さえる。 $∣ f (x) ∣ \leq q (∣ x ∣)$ である。 $B$ を多項式時間で検証する非決定性機械（あるいは検証者）に $f (x)$ を入力すれば、全体の時間は $q (∣ x ∣)$ の多項式、したがって $∣ x ∣$ の多項式で、 $x \in A ⟺ f (x) \in B$ を判定できる。よって $A \in NP$ 。

イ（誤り）. $A = \emptyset \in P$ 、 $B = HALT$ とする。 $HALT$ に属さない固定した列 $z$ （たとえばすぐに無限ループする機械の符号）をとり、 $f (x) = z$ とおくと、 $f$ は定数関数で多項式時間計算可能であり、 $x \in \emptyset ⟺ f (x) \in HALT$ （両辺とも偽）なので $\emptyset \leq_{p} HALT$ 。しかし $HALT$ は決定不能なので $P$ に属さない。

ウ（正しい）. $L \neq = \emptyset$ , $L \neq = Σ^{*}$ より $y \in L$ , $z \in / L$ がとれる。任意の $A \in P$ に対し、 $f (x) = y (x \in A)$ , $f (x) = z (x \in / A)$ と定めると、 $A$ の判定が多項式時間でできるので $f$ も多項式時間計算可能で、 $x \in A ⟺ f (x) \in L$ 。よって $A \leq_{p} L$ 。 $L \in P$ と合わせて $L$ は $P$ 完全。

エ（誤り）. もし $SAT \leq_{p} Σ^{*}$ なら、充足不能な論理式 $φ$ （たとえば $p \land \neg p$ ）について $φ \in / SAT$ なので $f (φ) \in / Σ^{*}$ となるが、そのような列はない。 $SAT \in NP$ なので $Σ^{*}$ は $NP$ 困難でない。

オ（正しい）. サヴィッチの定理より $NL \subseteq SPACE (lo g^{2} n)$ 。領域階層定理より $lo g^{2} n = o (n)$ なので $SPACE (lo g^{2} n) ⊊ SPACE (n) \subseteq PSPACE$ 。よって $NL ⊊ PSPACE$ 。

カ（正しい）. 任意の $A \in NP$ をとり、 $A$ の多項式時間検証者 $R$ と多項式 $q$ を $x \in A ⟺ \exists u (∣ u ∣ \leq q (∣ x ∣), R (x, u) = 1)$ となるようにとる。入力 $x$ に対し、機械 $M_{x}$ を「長さ $q (∣ x ∣)$ 以下のすべての $u$ について $R (x, u)$ を調べ、 $1$ となる $u$ が見つかれば停止し、見つからなければ無限ループする」ものとする。 $M_{x}$ の符号は $x$ を埋め込むだけなので $∣ x ∣$ の多項式時間で書き出せ、 $f (x) = ⟨ M_{x}, ε ⟩$ は多項式時間計算可能である。そして $x \in A ⟺ M_{x}$ が停止 $⟺ f (x) \in HALT$ 。よって $A \leq_{p} HALT$ であり、 $HALT$ は $NP$ 困難（ $NP$ には属さないので $NP$ 完全ではない）。

キ（誤り）. $L$ が $EXP$ 完全で $L \in P$ とすると、任意の $A \in EXP$ について $A \leq_{p} L$ であり、 $P$ は $\leq_{p}$ で下に閉じている（多項式の合成は多項式）ので $A \in P$ 。よって $EXP \subseteq P$ となるが、時間階層定理より $P \subseteq DTIME (2^{n}) ⊊ DTIME (2^{2 n}) \subseteq EXP$ なので矛盾する。

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

別解

ア. 正しい。 $f$ を $A \leq_{p} B$ の帰着とし、 $B \in NP$ の非決定性多項式時間機械 $N$ をとる。 $x$ に対し $f (x)$ を多項式時間で計算し（長さは $∣ x ∣$ の多項式で抑えられる）、 $N$ を $f (x)$ に適用する。これは $A$ を判定する非決定性多項式時間機械なので $A \in NP$ 。

イ. 誤り。 $A = \emptyset \in P$ 、 $B = HALT \in / P$ （判定不能）とすると、 $f (x) =$ （ $HALT$ に属さない固定の列）で $A \leq_{p} B$ だが $B \in / P$ 。

ウ. 正しい。 $L \in P$ で $y_{1} \in L$ 、 $y_{0} \in / L$ をとる（ $L \neq = \emptyset, Σ^{*}$ より存在）。任意の $A \in P$ に対し、 $A$ を判定してから $y_{1}$ または $y_{0}$ を出力する写像 $f$ は多項式時間で、 $x \in A ⟺ f (x) \in L$ 。よって $L$ は $P$ 困難、かつ $L \in P$ なので $P$ 完全。

エ. 誤り。 $A \leq_{p} Σ^{*}$ なら、すべての $x$ で $f (x) \in Σ^{*}$ だから $x \in A$ がすべての $x$ で成り立ち $A = Σ^{*}$ 。 $\emptyset \in NP$ は $Σ^{*}$ に帰着できないので、 $Σ^{*}$ は $NP$ 困難ではない。

オ. 正しい。サヴィッチの定理により $NL \subseteq DSPACE (lo g^{2} n)$ 。空間階層定理により $DSPACE (lo g^{2} n) ⊊ DSPACE (n) \subseteq PSPACE$ なので $NL ⊊ PSPACE$ が証明されている。

カ. 正しい。 $A \in NP$ に対し、 $A$ は決定可能なので、 $A$ を判定するチューリング機械 $M_{A}$ から、入力 $x$ について $M_{A}$ が受理すれば停止し、拒否すれば無限ループする機械 $M_{A}^{'}$ を作る。 $f (x) = ⟨ M_{A}^{'}, x ⟩$ は多項式時間（実際は $∣ x ∣$ に線形）で計算でき、 $x \in A ⟺ f (x) \in HALT$ 。

キ. 誤り。もし $B \in P$ が $EXP$ 完全なら、すべての $A \in EXP$ が $B$ に多項式時間帰着できるので $A \in P$ 、すなわち $EXP \subseteq P$ 。しかし時間階層定理により $P ⊊ EXP$ が証明されているので矛盾。

よって正しいものはア, ウ, オ, カ。

この問題の確認

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

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

確認の方法について

間違いを報告する

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