P=NP問題の証明の問題点
from P=NP 問題
P=NP問題の証明の構造は雁字搦めになっている
$ {\rm P}={\rm NP}ならば、暗号論的ハッシュ関数が存在しないことがわかる
関数の計算が多項式時間で終わるため暗号論的ハッシュ関数の逆関数の計算は$ {\rm NP}問題ではある
仮定より、$ {\rm P}={\rm NP}なので暗号論的ハッシュ関数の逆関数の計算は$ {\rm P}になる
よって暗号論的ハッシュ関数の逆関数は多項式時間で計算できる
それはもはや暗号論的ハッシュ関数ではない
対偶を取ると
暗号論的ハッシュ関数が存在すれば$ {\rm P}\ne{\rm NP}
ところが以下のことが証明されている
暗号論的ハッシュ関数が存在すると$ {\rm P}\ne{\rm NP}を自然な証明で証明することが出来ない
自然な証明の中で使われる性質は多項式時間内に検査可能なもの
より計算困難な性質を用いて$ {\rm P}\ne{\rm NP}を示す必要がある