P, NP, NP完全, NP困難
NP完全とNP困難の違いがわかってない自分をようやく卒業できました。
ソースはWikipedia。適当にまとめるので、詳しく知りたい人は自分でWikipediaの記事見てください。
NP問題
まず、一番わかってないといけないのが、NPとは何かということで
であるということ。
つまり、NP問題は多項式では解けない問題ではなく、「非決定性チューリングマシンによって多項式時間で解ける問題である」ということ。
非決定性チューリングマシンとは、今いる状態から次の状態に行く選択肢が複数あった時に常に解に近づく選択肢を選べる機械だと思えば良い。ここら辺は正規表現の実装とかオートマトン思い出すしかない。
問題空間を探索木としてとらえると、神のようなヒューリスティクス関数によって解のある子ノードにいけると考えたときに多項式時間で到達可能な問題である。つまり、解のある場所の深さが多項式で表せるともいえる。
こういう問題空間でもコンピュータは決定性チューリングマシンだから、木の探索をするしかなく、その時点でO(木の分岐数^深さ)になり多項式時間で解けない。だから、NPが非多項式時間なイメージを持っちゃっていても誤解に気付かないのだと思う。
だから、「P⊆NP」である。
P≠NP予想は、あくまで「P＝NP」でなく「P⊂NP」だと予想している。
