多項式時間多対一帰着の性質

$\leq_{p}$ の推移性、補集合への移行 $A \leq_{p} B \Rightarrow A \leq_{p} B$ 、「 $A \leq_{p} B$ かつ $B \in P$ （ $NP$ ）なら $A \in P$ （ $NP$ ）」、 $A \in P$ なら $\emptyset, Σ^{*}$ 以外の任意の $B$ に帰着できることなどを証明・判定し、成り立たない主張（逆向き）を見分けられる

前提

チューリング機械の動作の追跡（大学数学オートマトン・形式言語）
計算量のオーダーの比較（大学数学アルゴリズムと計算量）

この技能までの道筋（21 技能）

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

決定性有限オートマトンの動作と受理判定（大学数学オートマトン・形式言語）
チューリング機械の動作の追跡（大学数学オートマトン・形式言語）
四則の混じった計算の順序（算数計算と数のきまり）
等間隔にならんだ数の和（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
等差・等比数列の和と Σ （数学B 数列）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
根号の乗除と加減（中学数学数と式）
指数の拡張と指数関数（数学II 指数関数と対数関数）
対数の定義と性質（数学II 指数関数と対数関数）
計算量のオーダーの比較（大学数学アルゴリズムと計算量）

説明

言語 $A, B \subseteq Σ^{*}$ について、 $A \leq_{p} B$ （ $A$ は $B$ に多項式時間多対一帰着できる）とは、多項式時間で計算できる関数 $f : Σ^{*} \to Σ^{*}$ で、すべての $x$ について $x \in A ⟺ f (x) \in B$ となるものが存在することです。直観的には「 $B$ が解ければ $A$ もほぼ同じ速さで解ける」、つまり「 $A$ は $B$ 以下の難しさ」を表します。この技能では、 $\leq_{p}$ の推移性・補集合への移行・ $P$ や $NP$ への所属の伝わり方を証明し、向きを逆にした成り立たない主張を見分けられるようになります。NP 完全性の議論など、問題の難しさを比べるあらゆる場面の土台です。

なぜそうしてよいのか

ここで $P$ は決定性チューリング機械が入力長 $n$ の多項式時間で判定できる言語全体、 $NP$ は非決定性チューリング機械が多項式時間で受理できる言語全体です。関数 $f$ を計算する機械は、入力 $x$ をテープに置いて動かし、停止したときのテープの内容を $f (x)$ とします。 $f$ が時間 $p (n)$ （ $p$ は多項式）で計算できるとき、テープ上には最初に入力の $∣ x ∣$ 個の記号があるだけで、ヘッドは 1 ステップに 1 マスしか動かず、1 ステップで新たに書ける記号は高々 1 個です。したがって $p (∣ x ∣)$ ステップの後に空白でないマスは高々 $∣ x ∣ + p (∣ x ∣)$ 個で、 $∣ f (x) ∣ \leq p (∣ x ∣) + ∣ x ∣$ となります。つまり帰着で写した後の入力も多項式の長さに収まります。そして多項式に多項式を代入したもの $q (p (n) + n)$ や多項式どうしの和は、また多項式です。これが以下の証明すべての核心です。

(1) $B \in P$ を時間 $q$ で判定する機械があれば、入力 $x$ に対し $f (x)$ を計算してから $f (x) \in B$ を判定すれば $x \in A$ がわかります。時間は $p (n) + q (p (n) + n)$ で多項式なので $A \in P$ です。 $NP$ でも、 $f (x)$ を決定的に計算してから $B$ を受理する非決定性機械を走らせれば同じ見積もりが通り、 $A \in NP$ です。(2) 推移性: $A \leq_{p} B$ を $f$ 、 $B \leq_{p} C$ を $g$ が与えるなら、 $g \circ f$ が $x \in A ⟺ f (x) \in B ⟺ g (f (x)) \in C$ を満たし、同じ見積もりで多項式時間です。(3) 補集合: $x \in A ⟺ f (x) \in B$ の両辺を否定すると $x \in A ⟺ f (x) \in B$ なので、同じ $f$ が $A \leq_{p} B$ を与えます（向きは変わりません）。

(4) $A \in P$ で $B \neq = \emptyset, Σ^{*}$ なら、 $y_{1} \in B$ と $y_{0} \in / B$ を 1 つずつ固定し、「 $x \in A$ を多項式時間で判定して、 $x \in A$ なら $y_{1}$ 、そうでなければ $y_{0}$ を出力する」関数 $f$ を作れば $A \leq_{p} B$ です（ $y_{0}, y_{1}$ は定数なので書き出しは定数時間）。つまり $P$ の言語は自明でないどんな言語にも帰着できてしまいます。ここから、逆向きの主張「 $A \leq_{p} B$ かつ $A \in P$ なら $B \in P$ 」が偽だとわかります。そのためには $P$ に属さない言語が 1 つあればよく、次の対角線論法で具体的に作れます。チューリング機械は遷移表という有限の情報で決まるので、 $Σ = {0, 1}$ 上の文字列で書き表せます（機械 $M$ を表す文字列を $⟨ M ⟩$ と書き、機械を表さない文字列は「何も受理しない機械」を表すと約束します）。そこで $D = {w \in Σ^{*} : w が表す機械は入力 w を受理しない}$ とおきます。もし $D$ を判定する（必ず停止して正しく受理・拒否する）機械 $M$ があったとすると、 $w = ⟨ M ⟩$ について「 $w \in D ⟺ M$ は $w$ を受理しない $⟺ w \in / D$ 」となり矛盾します。よって $D$ はどんな機械でも判定できず、とくに $D \in / P$ です。また $\emptyset, Σ^{*} \in P$ なので $D \neq = \emptyset, Σ^{*}$ であり、(4) より ${0} \leq_{p} D$ です。 $\leq_{p}$ は「易しい側 $\leq$ 難しい側」なので、易しさ（所属）は右から左へ（ $B$ から $A$ へ）、難しさ（非所属）は左から右へ（ $A$ から $B$ へ）しか伝わりません。

手順

主張に現れる帰着 $A \leq_{p} B$ の向きを確かめ、「左が易しい側、右が難しい側」と読む
所属（ $\in P$ , $\in NP$ ）は右から左へ伝わる: $B \in P \Rightarrow A \in P$ 、 $B \in NP \Rightarrow A \in NP$ 。非所属はその対偶で左から右へ: $A \in / P \Rightarrow B \in / P$ 、 $A \in / NP \Rightarrow B \in / NP$
帰着の組み合わせを整理する: $A \leq_{p} B, B \leq_{p} C \Rightarrow A \leq_{p} C$ （ $g \circ f$ を使う）、 $A \leq_{p} B \Rightarrow A \leq_{p} B$ （同じ $f$ を使う）
証明では、帰着関数の出力長が $∣ f (x) ∣ \leq p (∣ x ∣) + ∣ x ∣$ （最初の $∣ x ∣$ 個に 1 ステップ高々 1 個ずつ書き足すだけ）で抑えられることと、多項式の合成 $q (p (n) + n)$ が多項式であることを使って計算時間を見積もる
向きが逆の主張には反例を作る: $A \in P$ は $\emptyset, Σ^{*}$ 以外の任意の $B$ に帰着できるので、 $A = {0}$ と、対角線論法で作った $P$ に属さない言語 $D$ を組み合わせる

例題

アルファベットを $Σ = {0, 1}$ とする。次のア〜オの主張のうち、どの言語 $A, B, C \subseteq Σ^{*}$ についても成り立つもの（反例が 1 つもないもの）をすべて選べ。

ア: $A \leq_{p} B$ かつ $B \leq_{p} C$ ならば $A \leq_{p} C$

イ: $A \leq_{p} B$ かつ $A \in P$ ならば $B \in P$

ウ: $A \leq_{p} B$ ならば $A \leq_{p} B$

エ: $A \leq_{p} B$ かつ $A \in / NP$ ならば $B \in / NP$

オ: $A \leq_{p} B$ ならば $B \leq_{p} A$

例題の解答

（手順 1）どの主張も $A \leq_{p} B$ 、すなわち「 $A$ が易しい側、 $B$ が難しい側」を仮定している。

ア（手順 3・4）: $A \leq_{p} B$ を時間 $p$ の $f$ 、 $B \leq_{p} C$ を時間 $q$ の $g$ が与えるとする。 $x \in A ⟺ f (x) \in B ⟺ g (f (x)) \in C$ であり、 $∣ f (x) ∣ \leq p (n) + n$ （入力 $n$ 個に 1 ステップ高々 1 個書き足すだけ）より $g \circ f$ の計算時間は $p (n) + q (p (n) + n)$ で多項式。よって常に成り立つ。

イ（手順 2・5）: 所属は右から左にしか伝わらないので、左の $A$ が $P$ に入っても $B$ については何もいえない。実際に反例がある。 $A = {0}$ とすると $A \in P$ 。 $B$ として、idea で対角線論法により作った言語 $D = {w : w が表す機械は入力 w を受理しない}$ をとる。 $D$ を判定する機械 $M$ があると $w = ⟨ M ⟩$ で「 $w \in D ⟺ w \in / D$ 」となり矛盾するので、 $D$ はどの機械でも判定できず $D \in / P$ 。また $\emptyset, Σ^{*} \in P$ だから $D \neq = \emptyset, Σ^{*}$ で、 $y_{1} \in D$ , $y_{0} \in / D$ を固定できる。 $f (x) = y_{1} (x = 0)$ 、 $f (x) = y_{0} (x \neq = 0)$ とすれば $f$ は多項式時間で計算でき、 $x \in A ⟺ f (x) \in D$ なので $A \leq_{p} D$ 。しかし $D \in / P$ 。よってイは成り立たない場合がある。

ウ（手順 3）: $x \in A ⟺ f (x) \in B$ の両辺を否定すれば $x \in A ⟺ f (x) \in B$ 。同じ $f$ で帰着できるので常に成り立つ。

エ（手順 2）: 「 $A \leq_{p} B$ かつ $B \in NP$ ならば $A \in NP$ 」の対偶である。この主張は、 $f (x)$ を決定的に時間 $p (n)$ で計算してから $B$ を受理する非決定性機械を時間 $q (p (n) + n)$ 走らせればよいので正しい。よって常に成り立つ。

オ（手順 5）: イと同じ $A = {0}$ , $B = D$ をとると $A \leq_{p} B$ 。もし $B \leq_{p} A$ なら、手順 2 により $A \in P$ から $B \in P$ となり $D \in / P$ に矛盾する。よってオは成り立たない場合がある。

以上より、常に成り立つのはア、ウ、エ。

答え:

ア, ウ, エ

よくある誤り

帰着の向きを逆に使ってしまう誤り。「 $A \leq_{p} B$ かつ $A \in P$ なら $B \in P$ 」とするのは誤りで（ $A = {0}$ , $B = D$ が反例）、正しくは「 $A \leq_{p} B$ かつ $B \in P$ なら $A \in P$ 」（所属は右から左へ伝わる）
補集合をとると帰着の向きが逆になると考え、 $A \leq_{p} B \Rightarrow B \leq_{p} A$ としてしまう誤り。正しくは同じ $f$ で $x \in A ⟺ f (x) \in B$ となり、 $A \leq_{p} B$ （向きはそのまま）
合成の時間を見積もるとき、 $g$ の入力長を元の $n$ としてしまい $g \circ f$ の時間を $p (n) + q (n)$ とする誤り。正しくは $g$ の入力は $f (x)$ で、その長さは $p (n) + n$ まで伸びうるので、時間は $p (n) + q (p (n) + n)$ （それでも多項式）
「 $P$ の言語は任意の言語に帰着できる」と $\emptyset, Σ^{*}$ を含めてしまう誤り。 $B = \emptyset$ なら $f (x) \in B$ となる $x$ がないので、 $A \neq = \emptyset$ のとき $A \leq_{p} \emptyset$ は成り立たない（ $B = Σ^{*}$ と $A \neq = Σ^{*}$ でも同様）。正しくは $y_{1} \in B$ , $y_{0} \in / B$ がとれる $B \neq = \emptyset, Σ^{*}$ に限る

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
$Σ = {0, 1}$ とし、言語とは $Σ^{*}$ の部分集合のこととする。言語 $L$ の補集合を $L = Σ^{*} ∖ L$ と書く。言語 $X, Y$ について、 $X \leq_{p} Y$ とは、多項式時間で計算できる全域関数 $f : Σ^{*} \to Σ^{*}$ で、すべての $x \in Σ^{*}$ について $x \in X ⟺ f (x) \in Y$ となるものが存在することとする。
いま、言語 $A, B$ について $A \in P$ 、 $B \in NP$ であることだけがわかっている。次のア〜オの言語のうち、それぞれに書かれた条件だけから「 $NP$ に属する」と必ず結論できるものをすべて選べ。
ア　ある言語 $H$ について $C \leq_{p} H$ かつ $H \leq_{p} A$ をみたす言語 $C$
イ　 $D \leq_{p} B$ をみたす言語 $D$
ウ　 $A \leq_{p} E$ をみたす言語 $E$
エ　 $F \leq_{p} A$ をみたす言語 $F$
オ　 $B \leq_{p} G$ をみたす言語 $G$

この技能を使う問題

この技能の次に学べること

停止問題と決定可能性（大学院数学計算理論・ラムダ計算）
計算量クラスの包含関係と完全問題（大学院数学計算理論・ラムダ計算）