はじめに
必要であれば、前回記事も読んでください。
NP完全問題というのは何かというと、ある問題Aが、
- 問題AがクラスNPに属する
- すべてのクラスNPに属する問題が、問題Aに多項式時間還元（帰着）可能である1
という２つの条件を満たすとき、問題AはNP完全問題である、というわけです。
「還元」についての詳しい説明は、以下の記事を参照してください。
1. を証明するのは比較的易しいのですが、2. が曲者なんですね。クラスNPに属する問題なんて山ほど（無数に？）あるので。
そこで、ある問題AがNP困難であることを示すためには、別の証明方法（多くの人はこっちを習って、演習をしたと思います）があるわけです。
問題Aは、あるNP完全問題Bから多項式時間還元可能である。
ということが証明されれば、問題AはNP困難です。
（ちなみに、この証明方法は、多項式時間還元の推移性を用いています。詳しくは前回記事参照。）
疑問
上の例を見ると、疑問が出てきます。
「最初のNP完全問題はどうやってNP完全だと証明されたのか」
という疑問です。
ご存じの方もいらっしゃるように、最初のNP完全問題は、充足可能性問題（SAT）と呼ばれる問題（らしい）です。
SATがNP完全問題であることは、1971年に示されました（Cook-Levinの定理）。
ですが、私はその証明をきちんと調べたことがありませんでした。
さすがに原著論文を読むのもめんどくさいな、と思っていたのですが、英語版Wikipediaに記事がありました。
が、割と説明を端折ってる部分とかもあって、読むのに時間がかかったので、補足しながら日本語で説明しようと思います。
充足可能性問題（SAT）とは
SATとは、論理式が与えられた時、変数の真偽を適切に割り当てることで、論理式全体の値を真にできるか（真にできるような変数への真偽割り当てが一つでも存在するか）という問題です。
この記事では、AND演算子を「$\cdot$」、OR演算子を「$+$」、NOT演算子を「$\lnot$」とします。
では、論理変数$x, y$に対して、次の論理式を考えてみましょう。
\begin{equation*}
(x+y)\cdot (x+\lnot y)
\end{equation*}
このとき、$x = \textrm{True}$（真）とすると、式全体の値も真となるので、充足可能です。
つまり、この式が入力である充足可能性問題の答えは「YES」です。
一方で、
\begin{equation*}
(x+y)\cdot (x+\lnot y)\cdot (\lnot x+y)\cdot (\lnot x+\lnot y)
\end{equation*}
なる式に対しては、$x, y$にどのように真偽を割り当てても、式全体の値が偽になります。これを充足不能（恒偽）と呼び、この式に対しては「NO」が答えです。
Cook-Levinの定理の（雑な）概要
計算複雑性理論に関する前回の記事では、多項式時間還元に関する記法と、NP完全の定義を説明しました。
それを用いると、充足可能性問題SATがNP完全であることを証明するには、
- $SAT\in \textrm{NP}$
- 任意のNP問題Aに対して、$A\leq^p_{m} SAT$
の２つを証明すればいいわけです。
前回記事でも説明したように、SATがクラスNPに属することは比較的容易に示せます。
ざっくり言うと、論理式の長さは有限なので、各変数の真偽の割り当てを実際に代入することによって、多項式時間でその割り当てで充足されているかが検証できるんですね。
問題の２番目がCook-Levinの定理の肝で、
- 任意のNP問題は、非決定性チューリングマシンで、多項式時間で解ける。
- 非決定性チューリングマシンが受理する入力が与えられた時のみ真になるような論理式が常に構成可能であれば、非決定性チューリングマシンの動作をシミュレートできることになる。
- この変換は、決定性チューリングマシンを用いて多項式時間で行うことが可能なので、任意のNP問題Aに対して、$A\leq^p_{m} SAT$が成り立つ。
- つまり、SATはNP困難問題である。
という論法で証明しています。
非決定性チューリングマシンの定式化
では、今回用いる非決定性チューリングマシン$M$を定義しましょう。
$M=<Q, \Sigma, b, s, F, \delta>$
ここで、
- $Q$ – 状態の有限集合
- $\Sigma$ – テープ記号の有限集合（入力記号も含む）
- $b$ – 空のセルであることを表す記号。（$b\in \Sigma$）。元記事では言及されてませんが、後に出てくる「各セルにはちょうど1つの記号が存在する」という性質を保つために定義しておきます。
- $s$ – 初期状態（$s\in Q$）
- $F$ – 受理状態の有限集合（$F\subseteq Q$）
- $\delta$ – 動作関数の集合
とします。
$M$への入力サイズを$n$とすると2、NP問題の定義より、多項式$p(n)$の時間（処理のステップ数と考えたほうがいいかも）以内で、$M$は受理か拒否かを判定します（そのような$p(n)$が存在します）。
$M$が受理する言語$L$を考えます。語$w\in L$が入力された時は必ず、また入力された時のみ、真になるような論理式を構成3すれば、考えているNP問題はSATに帰着可能であることがわかります。
次回
次回記事で実際の証明を行います。
コメント