読者です 読者をやめる 読者になる 読者になる

yamaguchi.txt

開発日記。備忘録代わりだよ。

計算困難さ、NP完全とは?

計算 備忘録

このブログは備忘録なので、自分が忘れないためにまとめる。


そもそも計算とは。
有限時間内にチューリングマシンで解ける問題。
他の計算可能の定義として、λ計算再帰関数などがある。

しかし、チューリングマシンにも解けない問題が存在し、例えば停止性問題。
「入力が停止するかどうかを判定するチューリングマシン」は存在しないということ。
証明は、もし上記のチューリングマシンが存在するとしたら「入力が停止するのなら停止せず、停止しなければ停止するチューリングマシン」が存在するが、これを入力として同じチューリングマシンに与えた場合、同一のチューリングマシンにも関わらず入力が停止すれば停止せず、停止しなければ停止するので矛盾が生じる。


また、チューリングマシンで解ける問題の中にも難易度があり、それがEXP,P,NPなど。

クラスPは決定性チューリングマシン多項式時間で解ける判定問題のクラス。
クラスNPは非決定性チューリングマシン多項式時間で解ける判定問題のクラス。
判定問題は、例えばSAT,HC、TSPなど

判定問題の中で入力と答えの候補を与えられたとき、答えが正しいかを決定性チューリングマシン多項式時間で検証できるクラスを考えると、クラスNPと一致するので、分かりやすいのでしばしばNPの説明として使われる。

NP完全、NP困難の違い。
NP完全とは、NPに属する問題でクラスNPのすべての問題から多項式時間還元可能な問題。
NP困難とは、NPに属する問題と比べ、同等以上に難しい。NPに属する場合は、NP完全と一致する。