はじめに
前回記事の続きです。
今回は、前回説明した方針に従って、実際に証明をします。
証明
論理式の変数
論理式の変数の添え字$i, j, k$を定義します。
- $i$ – テープヘッドの位置。$-p(n) \leq i \leq p(n)$となる整数。初期位置が$i = 0$で、左に移動すると$-1$、右に移動すると$+1$される。
- 左右$p(n)$だけの長さがあれば十分。もしそれより多く必要だとすると、テープヘッドの移動だけで$p(n)$ステップを超えてしまう。
- $j$ – 記号（$j \in \Sigma$）。
- $k$ – 今のステップ数。全体で$p(n)$なので、$0\leq k\leq p(n)$です。
なお、それぞれの添え字と、$q\in Q$の個数について、以下のような計算ができます。
| 文字 | 個数（何通りあるか） | 個数（オーダー記法だと） | 個数の理由 |
|---|---|---|---|
| $i$ | $2\cdot p(n) + 1$ | $O(p(n))$ | $-p(n) \leq i \leq p(n)$だから。 $i=0$の場合も数える。 |
| $j$ | $|\Sigma|$ | $O(1)$ | 記号の種類。 $|\Sigma|$は定数と考えて、オーダー記法では考慮しない。 |
| $k$ | $p(n) + 1$ | $O(p(n))$ | $0\leq k\leq p(n)$だから。 |
| $q$ | $|Q|$ | $O(1)$ | 状態数。 $|Q|$は定数と考えて、オーダー記法では考慮しない。 |
以上の添え字を用いて、以下の変数を使った論理式を考えることになります。
| 変数 | 意味 | 個数（何通りあるか） | 個数の理由 |
|---|---|---|---|
| $T_{i, j, k}$ | ステップ$k$のとき、位置$i$のセルに文字$j$があるなら真になる変数 | $O(p(n)^2)$ | $i$の個数$\cdot j$の個数$\cdot k$の個数 $=O(p(n))\cdot O(1)\cdot O(p(n))$ |
| $H_{i, k}$ | ステップ$k$のとき、テープヘッドが位置$i$にあるなら真になる変数 | $O(p(n)^2)$ | $i$の個数$\cdot k$の個数 $=O(p(n))\cdot O(p(n))$ |
| $Q_{q, k}$ | ステップ$k$のとき、マシン$M$の状態が$q$であるなら真になる変数 | $O(p(n))$ | $q$の個数$\cdot k$の個数 $=O(1)\cdot O(p(n))$ |
次に、以上の変数を用いると、非決定性チューリングマシン$M$についてのどのような命題が記述できるかを示します。
なお、以下に出てくる$$\bigvee_{条件式}$$とか$$\bigwedge_{条件式}$$とかは、それぞれ論理和、論理積の複数個バージョンです。
| 式番号 | 論理式 | 意味 | 個数（何通りあるか） |
|---|---|---|---|
| 1 | $T_{i, j, 0}$ | 時刻$0$で、セル$i$の上には記号$j$がある。 | $O(p(n))$ |
| 2 | $Q_{s, 0}$ | $M$の初期状態は$s$である。 | $1$ |
| 3 | $H_{0, 0}$ | テープヘッドの初めの位置は$i = 0$である。 | $1$ |
| 4 | $\neg T_{i, j, k} \lor \neg T_{i, j’, k}$ $(j \neq j’)$ | 時刻$k$、セル$i$に異なる記号$j, j’$の両方が存在することはない。 | $O(p(n)^2)$ （$j, j’\in \Sigma$の組み合わせは、オーダー記法では考慮しないことに注意） |
| 5 | $$\bigvee_{j\in\Sigma}T_{i, j, k}$$ | 時刻$k$に、セル$i$には少なくとも一つの記号が存在する | $O(p(n^2))$ |
| 6 | $T_{i, j, k}\wedge T_{i, j’, k+1} \rightarrow H_{i, k}$ $(j\neq j’)$ | セル$i$の記号が時刻$k$から$k+1$で書き換えられたのなら、時刻$k$にテープヘッドはセル$i$を指していた。 | $O(p(n)^2)$ |
| 7 | $\neg Q_{q, k} \lor \neg Q_{q’, k}$ $(q \neq q’)$ | 時刻$k$では、異なる状態$q, q’$の両方であることはない。 式4と似た考え方。 | $O(p(n))$ |
| 8 | $$\bigvee_{q\in Q}Q_{q, k}$$ | 時刻$k$に、少なくとも一つの状態が存在する。 式5と似た考え方。 | $O(p(n))$ |
| 9 | $\neg H_{i, k} \lor \neg H_{i’, k}$ $(i \neq i’)$ | 時刻$k$に、テープヘッドは$i, i’$の両方を指し示すことはない。 式4と似た考え方。 | $O(p(n)^3)$ ・$i, i’$の組み合わせ（入れ替えたものは同じとみなす）は、 \begin{align*} &\binom{p(n)}{2}\\ &=\frac{p(n)\cdot (p(n) – 1)}{2}\\ &=O(p(n)^2) \end{align*} であることに注意。 |
| 10 | $$\bigvee_{-p(n)\leq i\leq p(n)}H_{i, k}$$ | 時刻$k$に、テープヘッドは少なくとも一つのセルを指し示す。 式5と似た考え方。 | $O(p(n)^2)$ |
| 11 | \begin{align*} &(H_{i,k}\wedge Q_{q,k}\wedge T_{i,\sigma,k})\rightarrow\\ &\bigvee_{((q,\sigma),(q’,\sigma’,d))\in\delta}(H_{i+d,k+1}\wedge Q_{q’,k+1}\wedge T_{i,\sigma’,k+1})\\ &\\ &(k\le p(n)) \end{align*} | 時刻$k$に、状態が$q$で、テープヘッドがセル$i$を指し、$i$に書かれた記号が$\sigma$であるとき、動作関数によって遷移可能な遷移先の少なくとも一つには遷移する。 | $O(p(n)^2)$ |
| 12 | $$\bigvee_{0\leq k\leq p(n)}\bigvee_{f\in F}Q_{f, k}$$ | $M$の動作中に、受理状態が少なくとも一つ存在する。 | $1$ |
さて、ここで、式4と5、7と8、9と10は、それぞれ合わせて考えると、「ちょうど一つ存在する」と言い換え可能なことに気を付けてください。
また、式11は、式4, 7, 9も合わせて考えると、結局遷移先は1つに限られることも覚えておいてください。
これらは後ほど、すべてを論理積でつなぎ合わせることになるからです。
それぞれの式の論理積
以上の変数について、それぞれの行で、全通りの論理積を取ることを考えます。
式1を例にすると、
$$\bigwedge_{-p(n)\leq i\leq p(n)}\bigwedge_{j\in\Sigma}T_{i, j, 0}$$
ということです（ただしこのとき、入力に従って、必要な変数には論理否定をつけたりします）。
このような論理式をそれぞれの行で考えると、以下の表のようになります。
| 式番号 | 意味 |
|---|---|
| 1 | テープの初期内容。 つまり、$M$への入力文字列。 |
| 4, 5 | 1つのセルには、常にちょうど1つの記号が存在する。 |
| 6 | 記号の書き換えは、テープヘッドが位置するところでのみ行える。 |
| 7, 8 | $M$は常にちょうど1つの状態にある。 |
| 9, 10 | テープヘッドは常にちょうど1つのセルを指す。 |
| 11 | $M$は動作関数に従って必ず遷移する。 「動作せずに留まる」ことはできない。 |
さらに、式2, 3, 12についても、非決定性チューリングマシン$M$ではどのような意味を持つか、言い換えておきます。
| 式番号 | 意味 |
|---|---|
| 2 | 初期状態$s\in Q$ |
| 3 | （テープヘッドの初期位置） |
| 12 | 受理状態の集合$F\subseteq Q$ |
論理式全体
さて、以上で定義した12種類の変数、そのそれぞれの式について論理積を取った12本の小さな論理式が定義されました。
次は、これらの12本の式すべての論理積をさらに取り、大きな1本の論理式を作ることを考えます。
式全体を示すことはしませんが、今までに示した式の意味ををすべて満たせば真、満たせなければ偽となる論理式が出来上がります。
この論理式、まさに非決定性チューリングマシンをシミュレートするようなものになっていることがわかります。
以上で、非決定性チューリングマシンをシミュレートする論理式が構成可能であることが示されました。
あとは、この変換が決定性チューリングマシンを用いて多項式時間でできることを示せばよいわけです。
論理式の大きさ
論理式全体が、多項式オーダーの長さであることを示します。
まず、表2を見ると、変数は合計$O(p(n)^2)$種類であることがわかります。
\begin{equation*}
O(p(n)^2)+O(p(n)^2)+O(p(n))=O(p(n)^2)
\end{equation*}
また、$O(p(n)^2)$個の変数をそれぞれ区別するには、$O(\log(p(n)))$の空間が必要です1。
\begin{equation*}
\log (O(p(n)^2))=O(\log (p(n)^2))=O(2\cdot \log (p(n)))=O(\log (p(n)))
\end{equation*}
さらに、論理式全体の節の数は、$O(p(n)^3)$です。
（表3の個数は、式9の$O(p(n)^3)$が最大だから）
つまり、論理式全体のサイズ（2進数で？）は、$O(\log (p(n))\cdot p(n)^3)$であることがわかり、これは多項式サイズ2である。
以上で、これらの変換が多項式時間で行えることがわかり、任意のNP問題$A$に対して、$A\leq^p_{m}SAT$であることがわかりました。
よって、SATはNP困難問題です。
また、クラスNPに属することも証明済みですので、SATがNP完全問題であることが示されました。
最後に
英語版Wikipediaであんまり説明されてなかったところは、自分なりに補足できたかなとは思います。特に変数とか節の個数の部分とかは頑張りました。
ですが、理解不足なところもあって、かなり厳密性や正確性に欠ける説明をしてしまっていると思います。
お詳しい方、ぜひWikipediaに日本語版の記事作ってください…
コメント