P=NP問題の証明

P=NP問題の証明

****P=NP問題の証明****

「神託により解が与えられる」を命題ｐとする。

「多項式時間で解ける」を命題ｑとする。

￢ｐ∧ｑ⇒P　　→　　￢P⇒￢（￢ｐ∧ｑ）　　　①

ｐ∧ｑ⇒NP　　→　　￢NP⇒￢（ｐ∧ｑ）　　　　②

背理法を用いる。P＝NPと仮定する。

￢P＝￢NP　　　③

①、②、③から

￢（￢ｐ∧ｑ）＝￢（ｐ∧ｑ）

￢ｐ∧ｑ＝ｐ∧ｑ

￢ｐ＝ｐ

となり、矛盾する。

従って、仮定P＝NPは誤りである。

よって、P≠NP　となる。

（証明終わり）