このブログは備忘録なので、自分が忘れないためにまとめる。
そもそも計算とは。
有限時間内にチューリングマシンで解ける問題。
他の計算可能の定義として、λ計算、再帰関数などがある。
しかし、チューリングマシンにも解けない問題が存在し、例えば停止性問題。
「入力が停止するかどうかを判定するチューリングマシン」は存在しないということ。
証明は、もし上記のチューリングマシンが存在するとしたら「入力が停止するのなら停止せず、停止しなければ停止するチューリングマシン」が存在するが、これを入力として同じチューリングマシンに与えた場合、同一のチューリングマシンにも関わらず入力が停止すれば停止せず、停止しなければ停止するので矛盾が生じる。
また、チューリングマシンで解ける問題の中にも難易度があり、それがEXP,P,NPなど。
クラスPは決定性チューリングマシンで多項式時間で解ける判定問題のクラス。
クラスNPは非決定性チューリングマシンで多項式時間で解ける判定問題のクラス。
判定問題は、例えばSAT,HC、TSPなど
判定問題の中で入力と答えの候補を与えられたとき、答えが正しいかを決定性チューリングマシンで多項式時間で検証できるクラスを考えると、クラスNPと一致するので、分かりやすいのでしばしばNPの説明として使われる。
NP完全、NP困難の違い。
NP完全とは、NPに属する問題でクラスNPのすべての問題から多項式時間還元可能な問題。
NP困難とは、NPに属する問題と比べ、同等以上に難しい。NPに属する場合は、NP完全と一致する。
