初心者が学ぶP,NP,NP困難(Hard),NP完全(Complete)とは（わかりやすく解説）
(※訂正のため更新 18/4/23)
論文を読んでいると言葉だけ出会うが、見なかったことにしている言葉なのでちゃんと知りたい。
スタート：全く意味がわかっていないレベル
ゴール：論文でその言葉の意味が掴めている状態
- 言葉の一般的な説明
- 分かりやすく説明
- Pの解説
- NPの解説
- NP困難 (NP-Hard)の解説
- NP完全 (NP-Complete)の解説
- 決定性、非決定性チューリングマシンの違い
- P, NPの違い
- NP困難, NP完全の違い
- P、NP、NP完全、NP困難と具体的例題
- 「P≠NP予想」とは
- 「総当りすればNPってPじゃないのか？」という疑問
- 終わりに
- 参考文献
言葉の理解や分かりやすさを重視しており、厳密性や詳細を割愛している部分も多く、
基本的には、数ヶ月後に忘れてしまうチンパンな私の為のメモとなっています。
勘違いやミスがあればご指摘いただけると幸いです。
まず、言葉の定義を確認する（ことで絶望する）
言葉の一般的な説明
Wikipediaから抜粋してみる
P
https://ja.wikipedia.org/wiki/P_(%E8%A8%88%E7%AE%97%E8%A4%87%E9%9B%91%E6%80%A7%E7%90%86%E8%AB%96)から抜粋。
NP
NP困難 (NP-Hard)
- 問題が「NPに属する任意の問題と比べて、少なくとも同等以上に難しい」ことである
- 正確にいうと問題 H がNP困難であるとは、「NPに属する任意の問題 Lが H へ帰着可能である」と定義される
https://ja.wikipedia.org/wiki/NP%E5%9B%B0%E9%9B%A3#cite_note-1から抜粋。
NP完全 (NP-Complete)
- クラスNP（Non-deterministic Polynomial）に属する決定問題（言語）で、
- かつ 任意のクラスNPに属する問題から多項式時間還元（帰着）可能なもののことである
https://ja.wikipedia.org/wiki/NP%E5%AE%8C%E5%85%A8%E5%95%8F%E9%A1%8Cから抜粋。
もうついていけない劣等感。
今回は、これらの定義や言葉がわかるようにしていく。
まず説明しやすい言葉に置き換えていく。
個人的な意見ですが、Pを理解しないとNPとかさっぱりだと思うので、根気強く読んでいけば分かるはず。
分かりやすく説明
まずはイメージを掴む。
関係図
これが頭に入っている方がイメージがつきやすい。
今現在、広く信じられている関係図は下記の通り。
細かくは後述していく。
問題の難易度
P、NP、NP完全、NP困難の順で計算の複雑度が高まる。
Pの解説
Pとは、多項式（Polynomial） を指す。
ざっくりしたイメージだと、Pは「現実的に（効率的に）解ける問題クラス」。
イメージは、「何もなくても多項式で余裕で解けるよ」
そして、「アルゴリズムで解ける各種問題において多項式時間で解決可能な問題はむしろ稀だよ」
定義では、「判定問題のうち、ある決定性チューリング機械によって多項式時間で解かれるものの全体をPで表す。」とあるが、特に青文字の言葉の意味に詰まって理解が進まない。
１つずつ説明してく。
判定問題とは
「0 / 1」、「yes / no」等を出力する二値分類問題
「判別問題ではない」問題は、例えば、「スタート地点から目的地までの所要時間や最短ルート」を求める問題だったりする。
決定性チューリングマシン（機械）とは
計算機を数学的に議論するための単純化・理想化された仮想機械。
データxに対して決まった（同じ）yが一意付けられて出力される。
厳密性を除き、突き詰めて考えると、現在の一般コンピュータもこれに相当するとされている。
多項式とは
多項式とは、定数と変数の積和から成り立つ式。(中学数学の復習）
例：
- f(n)=an+c
- f(n)=an^2+bn+c
- f(m,n)=mn+c
多項式以外で言えば、「指数関数」。
指数関数とは、底に対して、指数部に変数を持つものを式。
例：
- f(n)=a^n
「多項式時間で解ける」とは
多項式時間で解けるとは、多項式を解ける時間（と同等の時間）を指す。
説明には整数倍を無視した表現：オーダー(O)を使う。(詳細は割愛）
O(n) ← これは多項式オーダーで解ける時間を指す
例えば、ダイクストラ法。
駅数nと路線本数mにおける最適な径路を求めるのはO(mn）となり、多項式時間で解ける。
O(2^n) ← これは指数オーダーで解ける問題を指す
これは次に説明するNPに属する（困難か完全かは言ってない）
ちなみに
多項式に関しては、nは整数レベルであればそのorderで解ける。
一方で、
指数関数に関しては、
- nが小さければ、多項式時間より早く解ける場合がある
- nが大きければ、計算時間は発散していく
P読み直し
ここまで来て定義を読み直してみる。
「0/1で解ける問題の内、解が一意付けされた数学的に理想的なマシンによって、多項式を解ける相当の時間で解かれる集合」となる。
なので0/1で解ける判定問題以外はPではないし、指数オーダーで解ける問題はPではない。
やっとNPを説明できる下準備が終わった。
NPの解説
NPとは、非決定性多項式時間（Non-deterministic Polynomial time）であり、Not Pではない。
定義は、「非決定性チューリングマシンによって多項式時間で解くことができる問題」かつ、「yes となる証拠が与えられたとき、その証拠が本当に正しいかどうかを多項式時間で判定できる問題」。
上述したPの説明までで上はかなり読めるようになっているはず。
初出の非決定性チューリングマシンについて説明を書く。
非決定性チューリングマシンとは
データxに対して決まった（同じ）yが一意付けられておらず、状態が確定しないことを指す。
現在の状態から次の状態への遷移選択において、解に近づく選択肢を選べる（解を求めるのに効率的な選択が毎回可能な）マシンである。
具体的には、量子コンピュータ、並列処理できる強力なコンピュータ、普通のコンピュータ。
量子コンピュータは、指数時間で解く問題を多項式時間で解けるようになったりすると言われている。
普通のコンピュータも非決定性チューリングマシンに属しているが、突き詰めると決定性チューリングマシンでもあるらしい。
NP困難 (NP-Hard)の解説
NP困難とは、NPに属しているかはわからないが、少なくともNP以上に複雑ということ。
復習になるが、「問題がNPに属しているかは不明」ということなので、例えば、その問題が判別問題であってもいいし、そうで無くてもよい。
定義の言葉を砕いていく。
まず、「問題が「NPに属する任意の問題と比べて、少なくとも同等以上に難しい」ことである」について。
NP困難な問題は、少なくともNP以上に複雑な計算であることを指す。
次に、「正確にいうと問題 H がNP困難であるとは、「NPに属する任意の問題 Lが H へ帰着可能である」と定義される」について。
これですが、定義なので「そうですか」という感想です。
つまり「どんなNPな問題も、NP困難な問題Hに帰着できる」それがNP困難だ、ということ。
他にも「NP困難問題を解ける多項式時間の機械がもしあれば、それを利用してNPに属するどの問題も多項式時間で解くことができる。」という主張などがあります。
NP完全 (NP-Complete)の解説
NP完全とは、NPかつNP困難。
NPの中では最も難しい問題である。
定義は「クラスNP（Non-deterministic Polynomial）に属する決定問題（言語）で、
かつ 任意のクラスNPに属する問題から多項式時間還元（帰着）可能なもののことである」。
大体理解できる言葉が並んでいるが、初出で「多項式時間還元」を知る。
多項式時間還元(polynomial-time reduction)とは
分かりやすく定理を説明したものをhttp://www.cs.tsukuba.ac.jp/~takahito/gcourse/part2.pdfより抜粋。
問題 A を１回の基本演算と同じ時間で解くアル ゴリズム α があれば，α をサブルーチンとして用いることで問題 B を多項式時間で解くことが できるとき，B は A に多項式時間還元可能であるという．
なので、このサブルーチンを探し当てることが重要とされている。
そもそもNP完全かどうかは証明が必要。
1971年にCookが、「充足可能性問題はNP完全」と証明済み。
これが多項式で解ければ、すべてのNP完全問題は多項式で解けることになる（が、現実はまだ解けていない）
決定性、非決定性チューリングマシンの違い
- 決定性チューリングマシンとは、
- データxに対して決まった（同じ）yが一意付けられて出力される。
- 非決定性チューリングマシンとは、
- データxに対して決まった（同じ）yが一意付けられておらず、状態が確定しない。
- 状態は、問題が効率的に解けるように毎回選択されていく。
なので非決定性チューリングマシンで解くとは、効率的な状態遷移性のあるアルゴリズムで解くことを意味する。
例えば、現在の状態Sから次の状態へN個の分岐（選択肢）があり、分岐の深さをHとする。
NP困難, NP完全の違い
表現を変えて、おさらい。
解きたい問題がAの場合、
つまり、問題AがNPに限ったものがNP完全で、NPに限らないがNP困難（限らないとは例えば、判定問題でも判定問題以外でも良い）。
P、NP、NP完全、NP困難と具体的例題
| P | ダイクストラ法 |
| NP（完全） | 部分和、ハミルトン閉路問題（全ての交差点を通過する経路があるか否かを解く問題、組み合わせ最適化問題）、充足性問題、３充足性、頂点被覆、ぷよぷよ、テトリス |
| NP困難 | 巡回セールスマン問題（都市間移動における総移動コストの最小化問題、問題の大きさは都市数）、ナップサック問題（部分和の一般化） |
「P≠NP予想」とは
一般に「P≠NP」信じられている。
NPはPを自明に含む。しかし、PはNPと等しくないと予想されている。
一方で、NP完全問題が一つでも多項式時間で解けることが証明ができると、これは棄却され、多項式時間還元の定理より、「P＝NP」となる。
「P＝NP」となれば、ハミルトン閉路問題 やナップサックもPとなり、多項式時間で解が得られるようになる。
ただ、「P≠NP」も「P＝NP」も証明に成功した者は今のところいない。
「総当りすればNPってPじゃないのか？」という疑問
「総当たりしたら各々は全て多項式時間で解けるからNPじゃなくてPじゃ無いか？」という疑問
実際、問題の複雑度次第。
それぞれの問題を多項式時間で解けたとしても、その候補数の増え方が多項式とは限らない。（「解ける」とは、「検証出来る」ということ）
終わりに
んー大枠はわかった。
しっくり来てないとこもあるが、一旦ここまで。
あとは３ヶ月後も思い出せることを祈る。
参考文献
http://zellij.hatenablog.com/entry/20110529/p1
http://www.msi.co.jp/nuopt/glossary/term_0a027b64f4f576567f9b9d047b9b8eaab194e903.html
https://ja.wikipedia.org/wiki/P_(%E8%A8%88%E7%AE%97%E8%A4%87%E9%9B%91%E6%80%A7%E7%90%86%E8%AB%96)
http://d.hatena.ne.jp/nsasaki/20110414/1302787792
https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q12150303292
https://ja.wikipedia.org/wiki/%E5%A4%9A%E9%A0%85%E5%BC%8F%E6%99%82%E9%96%93
https://ja.wikipedia.org/wiki/%E6%8C%87%E6%95%B0%E9%96%A2%E6%95%B0%E6%99%82%E9%96%93
http://techtipshoge.blogspot.jp/2011/06/nnp_12.html
http://www.ms.u-tokyo.ac.jp/~kazushi/course/public_lecture_2007.pdf
https://kotobank.jp/word/%E5%A4%9A%E9%A0%85%E5%BC%8F%E6%99%82%E9%96%93-1813320
http://d.hatena.ne.jp/nsasaki/20110414/1302787792
http://www.cs.tsukuba.ac.jp/~takahito/Gcourse/part2.pdf
http://d.hatena.ne.jp/nsasaki/20110426/1303807572
http://techtipshoge.blogspot.jp/2011/06/nnp.html
https://ja.wikipedia.org/wiki/NP%E5%9B%B0%E9%9B%A3
