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

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

$Σ = {0, 1}$ とし、言語とは $Σ^{*}$ （空列を含む $Σ$ 上の有限列全体）の部分集合のこととする。言語 $A$ の補集合を $A = Σ^{*} ∖ A$ と書く。言語 $A, B$ に対し、多項式時間で計算できる全域関数 $f : Σ^{*} \to Σ^{*}$ であって、すべての $x \in Σ^{*}$ について
$x \in A ⟺ f (x) \in B$
をみたすものが存在するとき、 $A \leq_{p} B$ （多項式時間多対一帰着可能）と書く。 $P$ は決定性チューリング機械で多項式時間で判定できる言語のクラス、 $EXP$ はある $k$ について時間 $2^{O (n^{k})}$ で判定できる言語のクラスとする。

次のア〜カのうち、正しい（証明できる）ものをすべて選べ。ただし、ア〜オでは $A, B, C$ は任意の言語とする。

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

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

ウ. $A \leq_{p} B$ かつ $B \leq_{p} C$ ならば $A \leq_{p} C$ である。

エ. $A \leq_{p} B$ ならば $A \leq_{p} B$ である。

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

カ. $P ⊊ EXP$ である。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

帰着 $A \leq_{p} B$ は「 $B$ が易しければ $A$ も易しい」ことを示す道具である。どちら向きの推論が成り立つかに注意して、成り立たないものには反例を探そう。

ヒント 2

反例には、決定不能な言語（停止問題）や、空集合のような極端な言語が使える。また、多項式どうしの合成は多項式であること、多項式時間の計算の出力の長さは多項式で抑えられることを使う。

ヒント 3

イは $A = {0}$ と停止問題、オは $B = \emptyset$ で考えてみよう。カは時間階層定理から従う。

答えと解説

答えを見る

ア, ウ, エ, カ

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

解説を読む

各選択肢を調べる。

ア（正しい）. $A \leq_{p} B$ を与える関数 $f$ が時間 $p (n)$ （多項式）で計算でき、 $B$ が時間 $q (n)$ （多項式）で判定できるとする。入力 $x$ （長さ $n$ ）に対し $f (x)$ を計算し、 $f (x) \in B$ かどうかを判定すればよい。 $∣ f (x) ∣ \leq p (n)$ （時間 $p (n)$ では $p (n)$ 文字までしか書けない）なので、全体の時間は $p (n) + q (p (n))$ で多項式。よって $A \in P$ 。

イ（誤り）. 反例: $A = {0}$ とし、 $B$ を停止問題（決定不能な言語）とする。 $B$ に属する列 $y_{1}$ と属さない列 $y_{0}$ を $1$ つずつ固定し、 $f (x) = y_{1} (x = 0)$ 、 $f (x) = y_{0} (x \neq = 0)$ とおくと、 $f$ は多項式時間で計算でき $A \leq_{p} B$ となる。 $A \in P$ だが $B$ は決定可能でさえないので $B \in / P$ 。

ウ（正しい）. $A \leq_{p} B$ を $f$ （時間 $p (n)$ ）、 $B \leq_{p} C$ を $g$ （時間 $q (n)$ ）が与えるとき、 $g \circ f$ は時間 $p (n) + q (p (n))$ で計算でき、 $x \in A ⟺ f (x) \in B ⟺ g (f (x)) \in C$ 。よって $A \leq_{p} C$ 。

エ（正しい）. $A \leq_{p} B$ を与える同じ $f$ について、 $x \in A ⟺ f (x) \in B$ の両辺を否定すると $x \in A ⟺ f (x) \in B$ 。よって $A \leq_{p} B$ 。

オ（誤り）. 反例: $A = {0} \in P$ , $B = \emptyset$ とする。 $A \leq_{p} B$ なら $0 \in A$ より $f (0) \in \emptyset$ となり矛盾。（イの構成が使えるのは、 $B$ に属する列と属さない列の両方があるときだけである。）

カ（正しい）. 時間階層定理により $DTIME (2^{n}) ⊊ DTIME (2^{2 n})$ などが成り立つ。任意の多項式 $p$ について $DTIME (p (n)) \subseteq DTIME (2^{n})$ なので $P \subseteq DTIME (2^{n}) ⊊ DTIME (2^{2 n}) \subseteq EXP$ 。よって $P ⊊ EXP$ 。

したがって正しいものはア, ウ, エ, カ。

別解

各選択肢を確かめる。

ア. 正しい。 $f$ を帰着とすると、 $x \in A ⟺ f (x) \in B$ 。 $B$ の判定機械を $f (x)$ に適用すればよい。 $f$ は多項式時間なので $∣ f (x) ∣ \leq q (∣ x ∣)$ （ $q$ は多項式）で、 $B$ の判定も多項式時間だから合計も多項式時間。よって $A \in P$ 。

イ. 誤り。 $A = \emptyset$ （ $\in P$ ）、 $B$ を判定不能な言語（例: 停止問題）とし、 $f (x) =$ ( $B$ に属さない固定の列)とすると $x \in A ⟺ f (x) \in B$ は常に偽同士で成り立つので $A \leq_{p} B$ 。しかし $B \in / P$ 。

ウ. 正しい。 $f$ , $g$ を多項式時間帰着とすると、 $x \in A ⟺ f (x) \in B ⟺ g (f (x)) \in C$ 。 $g \circ f$ は、 $∣ f (x) ∣ \leq q (∣ x ∣)$ なので多項式時間で計算でき、全域。

エ. 正しい。同じ $f$ を使えば、 $x \in A ⟺ f (x) \in B$ の両辺を否定して $x \in A ⟺ f (x) \in B$ 。

オ. 誤り。 $B = \emptyset$ とし、 $A = Σ^{*} \in P$ とすると、 $x \in A$ は常に真だが $f (x) \in \emptyset$ は常に偽なので、そのような $f$ は存在しない。 $B = Σ^{*}$ と $A = \emptyset$ でも同様。

カ. 正しい。時間階層定理により $DTIME (2^{n})$ に属するが、 $DTIME (n^{k})$ （どの $k$ についても）には属さない言語が存在する。したがって $P ⊊ EXP$ 。

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

この問題の確認

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

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

確認の方法について

間違いを報告する

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