悪魔の証明に挑む計算複雑性理論のわかりやすい（つもり）の解説

PとNPと聞くと胃が痛くなる人はどれくらいいるでしょうか。あ、俺もそうです。

一般にないことを証明するのは非常に困難だ。それを人々は悪魔の証明と呼ぶ。

悪魔の証明とは、「ある事実・現象が『全くない(なかった)』」というような、それを証明することが非常に困難な命題を証明すること。例えば「アイルランドに蛇はいる」ということを証明するとしたら、アイルランドで蛇を一匹捕まえて来ればよいが、「アイルランドに蛇はいない」ということの証明はアイルランド全土を探査しなくてはならないので非常に困難、事実上不可能であるというような場合、これを悪魔の証明という。
http://d.hatena.ne.jp/keyword/%B0%AD%CB%E2%A4%CE%BE%DA%CC%C01

ある問題を現実的な計算量で解くアルゴリズムが存在するか否か―存在しないことが判明してしまえば、その問題の効率的なアルゴリズムを探すことは意味がなくなってしまうので、その問題を一部制限することで解けるようにするなどのアプローチを試すきっかけになるだろう。しかし、存在しないことを証明するというのは、先ほども述べたように悪魔の証明だ。

これを解決したのが計算複雑性理論であり、 $P$ とか $NP$ とかだが、結局のところよく分からない。俺自身学部で習った時は、なんのことやら判らなかった。

しかし、判ってみたら、なんてことなかった。このエントリでは計算複雑性の考え方を説明したいと思う。

PとNPって何だ?

$P$ とか $NP$ とは問題の「集合」のことで、

$P$: 現実的に解ける計算量で正確な答えが出せるアルゴリズムが存在する判定問題の集合
$NP$: ある条件さえ整えば、現実的に解ける計算量で正確な答えが出せるアルゴリズムが存在する判定問題の集合

のことだ。「現実的な計算量とは何か」やらNPの「ある条件」などはとりあえず片隅に置いておきまましょう。重要なのは、二つとも問題に対する現実的な計算量のアルゴリズムが存在することが条件となっている。明らかに $P \subset NP$ である。しかし、問題が容易に解けるかどうかしか説明していない。では解けないことを証明するにはどうするのだろうか。ここで $NP- hard$ という問題の集合が登場するのだ。

現実的な計算量で解けないことを証明する

$NP-hard$ とは、

$NP-hard$: あらゆる $NP$ から現実的に解ける計算量で変換できる判定問題の集合

のことだ。ここで $NP-hard$ の問題が1問でも現実的な計算量で解けると仮定しよう。このとき、あらゆる $NP$ に属する問題は、その問題に現実的な計算量で変換できるので、 $NP$ すべての問題が現実的な計算量で解けることになり、 $P$ と $NP$ は同じ集合を指すことになる。すなわち、 $P = NP$ だ。

一方、今の話の対偶を取ってみよう、「ある $NP-hard$ に属する問題が現実的な計算量で解けるならば、 $NP$ すべての問題が現実的な計算量で解ける」の対偶は、「ある $NP$ の問題が現実的な計算量で解けないならば、すべての $NP-hard$ に属する問題は現実的な計算量で解けない」、すなわち $NP-hard$ の問題は、一問たりとも $P$ に属さないことになる。