PとNPとNP完全の関係を,もう一度教えてください.
「P」は,決定性テューリング機械を使って多項式時間で解くことができる,“問題の集合”です.無限集合です.
「NP」は,非決定性テューリング機械を使って多項式時間で解くことができる“問題の集合”です.無限集合です.P⊆NPです.
「NP完全」を説明する前に,「NP困難」を取り上げておきましょう.「NP困難」の“問題”というのは,もしそれが決定性テューリング機械を使って多項式時間で解くことができるならば,NPに属するどの問題も,決定性テューリング機械を使って多項式時間で解くことができるというものです.
「NP完全」の“問題”というのは,NPに属していて,かつNP困難であるものをいいます.NP完全の問題というのはいくつもあることが分かっており,その集合をNPcompと書くと,NPcompも無限集合ですし,NPcomp⊆NPです.
このように,関係としては,「P」と「NP」と「NP完全の集合」の3つを考えるといいでしょう.
NP完全の問題って,どうやって証明するのですか?
上の定義に基づいて,SAT(充足可能性問題)と呼ばれる問題が,NP完全であることが証明されました.原文を読んだわけではないのですが,決定性テューリング機械の動作を,SATの論理式で規定するという証明を読んだことがあります.
それ以後は,多項式時間還元可能性という概念を用いて,他のいろいろな問題もまたNP完全であることが証明されていきました.
多項式時間還元可能性?
2つの問題P1, P2を考えます.それぞれ,個別問題の集合である点に注意してください.
ここで,P1からP2への写像mapping fをうまく構成でき,さらにいくつかの条件を満たすものとします.条件を順に書きます.
- P1に属するどんな個別問題p1に対しても,f(p1)を求めることができ,かつこれはP2に属します.あ,これはfがP1からP2への写像であるための必要十分条件です.補足ですが,全射とか単射とかは要求しません.言い換えると,fの定義域はP1全体で,値域はP2の部分集合となります.
- 問題P1における個別問題p1の真偽*1と,問題P2における個別問題f(p1)の真偽が一致します.
- p1から,写像fによりp2に変換するのに要する時間計算量は,p1の問題サイズの多項式以下です.
上記の2番目と3番目の条件に出てくるp1は,P1に属する「ある要素」ではなく,「任意の要素」です.
このような写像fが存在すれば,P1はP2に多項式時還元可能であると呼ばれます.
多項式時間還元可能と,NP完全の関係は?
- P1として,NP完全であることがすでに証明されている問題を選びます.
- P2として,NP完全であることを証明したい問題を選びます.P2がNPに属することは,あらかじめ示しておきます.
- そして,上のように,多項式時間還元可能である根拠となるような写像fを示します.
そうすると,P2も,NP完全であることが証明されたことになります.
というのも,さらにP2がPに属すると仮定します.なお,P1がPに属することは,仮定しません.
次に,P1に属する任意の個別問題p1について,f(p1)を求め,P2の個別問題として,決定性テューリング機械を使って多項式時間でその真偽を判定します.
そしてその結果は,P1の個別問題p1の真偽と同じです.言ってみれば,以上のステップで,P1に属するどんな個別問題も,決定性テューリング機械を使って多項式時間で解けることになります*2.はい,P1がPに属するということです.
そうすると,NP完全の定義から,NPに属するどの問題も,P1,P2を経由して,決定性テューリング機械を使って多項式時間で解くことができることになります.上記の1〜3により,P2もまたNP完全になるということです.
*1:計算理論で考える「問題」は,値を求める問題であっても,真偽を求める問題に変換可能です.詳細は,また別の機会に書きます.
*2:多項式時間還元可能性については,ファンタジーの法則 雑感(改訂あり) - わさっきでも取り上げました.問題を真偽判定に限定し,変換前と変換後で,個別問題の真偽を一致させることで,「別世界」から「こちらの世界」に戻る際のコストを考えずに済みます.