blog2011年6月11日土曜日NとかNPとか困難とか完全とかいろいろ知識がついてきたので理解できるかなと思ったので、勉強しなおした。クラスNとNPについて。ともに判定問題の複雑性クラスである。対象となる問題は、「Yes」、「No」で答えられる問題のみ。判定問題の例は、ある条件を満たす整数(a,b)の組はあるか?第n番目のフィボナッチ数はm以上か?など。P」の略と勘違いしてしまいがちだが、これは大きな間違い。どっちのクラスも多項式時間で解けるが、「何を使って多項式時間で解けるか」が違う。クラスPの問題は、決定性チューリングマシンを使って多項式時間で解ける。クラスNPの問題は、非決定性チューリングマシンを使って多項式時間で解ける。決定性チューリングマシン(TM)とは?計算機を数学的に扱うために、単純化されたモデル。・テープ・テープの情報を読むヘッド・機械の内部状態を記憶するメモリから成り立つ。"決定性"の意味は、テープから読みとった情報がxで、メモリに記憶された状態がyの場合は、毎回決まったことを実行するということ。非決定性チューリングマシン(NTM)とは?テープから読みとった情報、メモリの内部状態が同じでも「毎回同じことを実行しない。次の遷移が決定されない。決定されないなら、どういう風に動くの?与えられた情報から、実行しうる処理のうち、最も効率的な処理を毎回選ぶことができる。組み合わせ最適化問題などで、今の状態から進むことのできる状態がK個ある場合、NTMは、最も早く最適解に到達できる状態へ遷移する。いうことで、分岐K、深さLの木データを探索する場合、TMの場合は、k^Lの計算が必要だが、NTMの場合は、LでOKということになる。ここで、注目すべきは、TMで多項式時間で解ける問題は、明らかにNTMでも多項式時間で解けるので、クラスPはクラスNPの部分集合ということである。多項式時間チューリング還元可能である」NP困難はNP完全と同等以上に難しい。