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

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

アルファベットを $Σ = {0, 1}$ とし、言語は $Σ^{*}$ の部分集合とする。 $A \leq_{p} B$ は多項式時間多対一帰着が存在することを表す（多項式時間で計算できる全域関数 $f$ で、すべての $x$ について $x \in A ⟺ f (x) \in B$ となるものがある）。 $P, NP, NL, coNL, PSPACE, NPSPACE, EXP$ は通常の多テープチューリング機械による計算量クラスとする。 $HALT$ はチューリング機械 $M$ と入力 $w$ の符号 $⟨ M, w ⟩$ のうち $M$ が $w$ で停止するもの全体（符号になっていない列は含まない）、 $TQBF$ は真である閉じた量化ブール式（冠頭形）の符号全体とする。

次のア〜キのうち、正しいと証明されている主張をすべて選べ。

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

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

ウ. $NL = coNL$ である。

エ. $TQBF \in NL$ である。

オ. $HALT$ は $\leq_{p}$ に関して $NP$ 困難である（すなわち、すべての $L \in NP$ について $L \leq_{p} HALT$ ）。

カ. $PSPACE \neq = NPSPACE$ である。

キ. $P ⊊ EXP$ である。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

各主張について、帰着の向き（易しいクラスへの所属は帰着の「先」から「元」へ伝わる）と、計算量の基本定理（Savitch の定理・Immerman–Szelepcsényi の定理・時間と領域の階層定理）のどれが使えるかを考える。

ヒント 2

イは反例を作る。エは $TQBF$ の $PSPACE$ 完全性と $NL ⊊ PSPACE$ を組み合わせる。オは「入力を無視して $x \in L$ を判定し、受理したときだけ停止する機械」の符号を作る写像を考える。

ヒント 3

ア・ウは成り立ち、イ・カは成り立たない。残りのエ・オ・キについて、 $NL \subseteq SPACE (lo g^{2} n) ⊊ PSPACE$ 、帰着を計算する時間と判定にかかる時間の違い、 $TIME (2^{n}) ⊊ TIME (2^{2 n})$ を確かめる。

答えと解説

答えを見る

ア, ウ, オ, キ

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

解説を読む

各主張を調べる。

ア（正しい）. $B$ を多項式時間で検証する非決定性機械 $N$ と、帰着 $f$ （多項式 $p$ 時間）をとる。入力 $x$ に対して $f (x)$ を計算し（長さは高々 $p (∣ x ∣)$ ）、 $f (x)$ に $N$ を走らせる非決定性機械は、多項式の合成で抑えられる時間で動き、 $x \in A ⟺ f (x) \in B$ なので $A$ を受理する。よって $A \in NP$ 。

イ（誤り）. 帰着は「易しい側から難しい側へ」向かうので、 $A$ が易しくても $B$ は易しいとは限らない。反例: $A = {1} \in P$ 、 $B = HALT$ とする。ただちに停止する機械 $M_{0}$ と、決して停止しない機械 $M_{1}$ の符号を固定し、 $f (1) = ⟨ M_{0}, ε ⟩$ 、 $x \neq = 1$ なら $f (x) = ⟨ M_{1}, ε ⟩$ とすれば $f$ は多項式時間で計算でき、 $A \leq_{p} HALT$ 。しかし $HALT$ は決定不能なので $P$ に属さない。

ウ（正しい）. Immerman–Szelepcsényi の定理により、 $s (n) \geq lo g n$ のとき $NSPACE (s (n))$ は補集合をとる操作で閉じている。特に $NL = coNL$ 。

エ（誤り）. $TQBF$ は対数領域帰着に関して $PSPACE$ 完全である。 $NL$ は対数領域帰着で閉じているので、 $TQBF \in NL$ なら $PSPACE \subseteq NL$ となる。一方、Savitch の定理より $NL \subseteq SPACE (lo g^{2} n)$ であり、領域階層定理より $SPACE (lo g^{2} n) ⊊ SPACE (n) \subseteq PSPACE$ 。よって $NL ⊊ PSPACE$ で矛盾する。

オ（正しい）. $L \in NP$ とし、 $L$ を決定する（常に停止する）決定性機械 $D$ を 1 つ固定する（ $NP \subseteq EXP$ なので、非決定性の選択をすべて試す機械でよい）。入力 $x$ に対し、機械 $M_{x}$ を「入力を無視して $D$ を $x$ 上で走らせ、受理なら停止し、拒否なら無限ループに入る」ものとする。 $⟨ M_{x}, ε ⟩$ は $D$ の記述（定数）に $x$ を書き込むだけなので、 $x$ の長さの多項式時間で計算できる。 $x \in L ⟺ M_{x}$ が $ε$ で停止する $⟺ ⟨ M_{x}, ε ⟩ \in HALT$ なので $L \leq_{p} HALT$ 。帰着の計算に $D$ の実行時間はかからないことに注意する。

カ（誤り）. Savitch の定理より $NSPACE (s (n)) \subseteq SPACE (s (n)^{2})$ なので、多項式の 2 乗は多項式であることから $NPSPACE \subseteq PSPACE$ 。逆の包含は明らかなので $PSPACE = NPSPACE$ 。

キ（正しい）. 時間階層定理より $P \subseteq TIME (2^{n}) ⊊ TIME (2^{2 n}) \subseteq EXP$ （ $n^{k} = o (2^{n})$ なので $P \subseteq TIME (2^{n})$ 、また $2^{n} lo g 2^{n} = o (2^{2 n})$ なので真の包含）。よって $P ⊊ EXP$ 。

以上より正しいものはア, ウ, オ, キ。

別解

各主張を確かめる。

ア（正しい）: $A \leq_{p} B$ の帰着 $f$ と、 $B$ を判定する多項式時間の非決定性チューリング機械 $N$ がある。入力 $x$ に対し $f (x)$ を多項式時間で計算し（ $∣ f (x) ∣$ は多項式で抑えられる）、 $N$ を $f (x)$ 上で走らせる。これは多項式時間の非決定性機械で、 $x \in A ⟺ f (x) \in B$ なので $A$ を判定する。よって $A \in NP$ 。 $A, B$ は任意の言語（自明な言語でもよい）で成り立つ。

イ（誤り）: $A = \emptyset \in P$ とし、 $B = HALT$ とする。 $B$ に含まれない固定の列 $y$ を使い、 $f (x) = y$ とすれば $A \leq_{p} B$ だが、 $HALT$ は決定不能なので $P$ に入らない。帰着の向きが逆（ $B \in P$ なら $A \in P$ が正しい）。

ウ（正しい）: Immerman–Szelepcsényi の定理により $NL = coNL$ は証明されている。

エ（誤り）: $TQBF$ は $PSPACE$ 完全。これが $NL$ に入るなら $PSPACE \subseteq NL$ となる。一方 $NL \subseteq SPACE (lo g^{2} n)$ （Savitch）で、空間階層定理により $SPACE (lo g^{2} n) ⊊ PSPACE$ なので矛盾する。したがって $TQBF \in / NL$ が証明されている。

オ（正しい）: $L \in NP$ を多項式時間 $p (n)$ で $L$ を判定する非決定性機械 $N$ とする。決定性機械 $M_{N}$ を、入力 $x$ に対して $N$ のすべての計算経路を $p (∣ x ∣)$ ステップまで調べ、受理経路があれば停止、なければ無限ループするものとして作る。 $x \mapsto ⟨ M_{N}, x ⟩$ は多項式時間で計算でき、 $x \in L ⟺ M_{N}$ が $x$ で停止。よって $L \leq_{p} HALT$ 。

カ（誤り）: Savitch の定理により $PSPACE = NPSPACE$ 。

キ（正しい）: 時間階層定理により $P ⊊ EXP$ は証明されている。

以上から、正しいと証明されているのはア、ウ、オ、キ。

この問題の確認

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

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

確認の方法について

間違いを報告する

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