むしゃくしゃしたのでNP完全とNP困難の話をする
はじめに
深夜3時. 大学院生は今日も不安を抱えながら勉強するふりをしている*1.
最近, NP完全とNP困難, NPに関して整理をした. 勉強していて驚いたことを紹介する.
発端は, WikipediaにあったNP困難について記載されているページの以下の一文である.
NP完全問題とは、NP困難であり、かつNPに属する問題である。
たしかに, 計算量理論の本とかwebを見ていると, NP困難な問題の集合はNPと交わっていて, しかもNPかつNP困難な問題がNP完全であるようなベン図の書き方になっている. しかし, NP困難とNP完全では, 変換と帰着で異なる操作を行っているはずである. (TODO: いい感じのベン図を書く)
事前知識
以下の文章では, オートマトンや決定性/非決定性チューリングマシンについての説明は行わない. 以下に参考書をあげておく.
ホップクロフトとウルマンの書いたオートマトンと言語理論の本. 全部読んだことはないが, オートマトンについて図式で説明があり, その拡張としてチューリングマシンの説明をしていた気がする.
オートマトン言語理論 計算論〈1〉 (Information & Computing)
- 作者: J.ホップクロフト,J.ウルマン,R.モトワニ,John E. Hopcroft,Jeffrey D. Ullman,Rajeev Motwani,野崎昭弘,町田元,高橋正子,山崎秀記
- 出版社/メーカー: サイエンス社
- 発売日: 2003/04/01
- メディア: 単行本
- 購入: 1人 クリック: 172回
- この商品を含むブログ (19件) を見る
- 作者: ジョン・E・ホッブクロフト,R・モトワニ,J・D・ウルマン,野崎昭弘,高橋正子,町田元,山崎秀記
- 出版社/メーカー: サイエンス社
- 発売日: 2003/08/13
- メディア: 単行本
- 購入: 3人 クリック: 22回
- この商品を含むブログ (11件) を見る
GaryとJohnsonの黒い本. 特に事前知識を必要としないので, 英語に抵抗がない人にとっては読みやすいと思う. 上の本と併読するとチューリングマシンの説明で躓かずに済む(この本ではオートマトンについての説明がないため, 特に非決定性チューリングマシンの定義が上の本とは若干異なる).
- 作者: Michael R. Garey,David S. Johnson
- 出版社/メーカー: W H Freeman & Co
- 発売日: 1979/01/15
- メディア: ペーパーバック
- 購入: 1人 クリック: 7回
- この商品を含むブログ (6件) を見る
判定問題, NP, NP完全, NP困難
まずは定義を簡単に説明しておく. 判定問題とは, 簡単には与えられた入力が, ある性質を満たしていれば1, 満たさないなら0を答える問題である.
問題\( \Pi \)が判定問題であるとは, 入力 \( x \in \Pi \) に対して, \( x \in \Pi_{\mathrm{yes}} \) なら1を, そうでないなら0を出力として求める問題である.
具体的な例として, 合成数判定問題がある. 合成数判定問題とは, 整数\( x \in \mathbb N \)が入力されたとき, \( x \) が合成数なら1を, そうでないなら (つまり, 素数であるなら) 0を出力とするような問題である. また, \( \Pi \) を判定するとは, 入力 \( x \in \Pi \) に対して, \( x \in \Pi_{\mathrm{yes}} \) なら1を返すことをいう.
次に, クラスNPについて説明する. NPとは, Non-deterministic polynomialの略で, 非決定性チューリングマシンで多項式時間で判定できる問題のクラスである. 非決定性チューリングマシンについての説明がない場合, 以下のように書かれることが多い.
判定問題 \( \Pi \) とする. 入力 \( x \in \Pi \) に対して, 任意の解の候補\( w \)が与えられたとき, 多項式時間で検証できるならば, \( \Pi \) はNPに属するという.
例として, 先ほど挙げた合成数判定問題を考えてみる. ここでは, 整数 \( n \in \mathbb N \) に対して, \( n \) が合成数のとき, \( w \) として \( n \) を割り切る数が与えられたと考える. 具体的には, 10が入力とすると, 解の候補として2が与えられたとき, 10は2で割り切れるので合成数であることが確かめられる. 一方で, 解の候補として3が与えられたとき, 10は3で割り切れないので, 3は不適切な候補だったことが確かめられる.
クラスNPの定義は, 合成数でない入力, 即ち \( x \in \Pi_{\mathrm{no}}\) (これは今の例でいえば \( x \) が素数であることを検証することに対応する) となるような入力について, 多項式時間で検証できるということを主張しているわけではない, ということに注意されたい. この記事の主題から外れるため本稿では触れないが, co-NPというクラスはそのような入力に対して, 多項式時間で検証できるような問題の集合として定義される.
NP完全とNP困難
判定問題 \( \Pi \) が以下を満たすとき, \( \Pi \) はNP完全であるという.
NP完全の定義が要求するのは, ①NPに属していることと, ②任意のNPに属する問題について, \(f\)の入力が\( \Pi'_{\mathrm{yes}}\)に入っている(yesインスタンスと呼ぶ)とき, かつそのときのみ \(\Pi\) のyesインスタンスに写すような変換\( f \)が存在すること, の2つのみである(また, このfを多項式変換とよぶ).
対して, NP困難の定義を見てみよう. ところで, ここでは(あとで説明する都合上)判定問題についてのNP困難の定義について述べる.
判定問題 \( \Pi \) が以下を満たすとき, \( \Pi \) はNP困難であるという.
- \(y \in \Pi\) に対して, \(y \in \Pi_{\mathrm{yes}}\) なら1, そうでないなら0を返す関数 \(g \colon \Pi \to \{0, 1\}\) が定数時間で計算できるとする. 任意の \( \Pi' \in\) NPに対して, \(g\) を用いて多項式時間で判定できる
ここで, \(g\) を使える以外の計算は決定性チューリングマシンと同じ操作しか出来ないものと考える.
明らかに, 問題 \(\Pi\) がNP完全ならば, \( \Pi \in \) NPかつ \(\Pi\) はNP困難である. 方針としては以下のとおりである.
NP完全性より, 任意の \(\Pi' \in\) NPのyesインスタンスから, \(\Pi\) のyesインスタンスに移すような多項式変換 \(f\) が存在する. \( x \in \Pi\) に対して \(x \in \Pi_{\mathrm{yes}}\) なら1, そうでないなら0を返す関数 \(g \colon \Pi \to \{0, 1\}\) を1回だけつかうことで, 任意の \(\Pi' \in\) NPを判定することができる. よって \(\Pi\) はNP困難.
しかし, 逆は未解決問題である*2. NP完全性を示す際には, 入力から入力へ写すような変換を計算するだけだった. 対して, NP困難性を示す際には, 定数時間で答えを返してくれる関数 \(g\) (オラクルという)を多項式回だけ使うことができるため, より強力な操作が可能なのである. 定義から考えると自然っぽいのだが, 意外と知られていないのではと思う. 僕も勉強するまで知らなかった. つまり, NPかつNP困難な問題の集合とNP完全な問題の集合の間には, 何があるかわからない(ないかもしれない)未解決な闇があるのだ. なんかかっこいい. 多分下の図のような感じ.
ここで, 発端の話題に戻ると,
NP完全問題とは、NP困難であり、かつNPに属する問題である。
という主張は, "NP困難かつNPに属するならNP完全である" というふうに読めるので修正したほうがいいのでは. と思ったという話(気が向いたら修正の要請を出そうかと思います).
