「P!=NP 予想、証明されるか ?」記事へのコメント

P != NP の重要性？

[deepsix (2374)]

昔から気になっていたので識者の方にお尋ねします。

Wikipediaにもあるように、現在の公開鍵暗号法式は「P != NP」が前提で、確認できていないが素因数分解や離散対数問題はPには含まれない事を頼りにしていると理解しています。
なのでもし「P = NP」が証明されると、現在の公開鍵暗号法式は安全ではなくなる事を意味する。ここまでは理解できます。

では「P != NP」が証明される事と、素因数分解や離散対数問題がPには含まれず、NPである事とはまた別の問題だと認識していますが違うのでしょうか？

つまり「P != NP」を証明しても、現状の「素因数分解って簡単にはでけへんと思うは、そうやろ？だからきっと安全やで」の世界からは一歩も前進していない。 理想郷はあるらしいが、ここがそうかは誰も知らずに幸せに暮らしているのと変わらないんじゃ無いんでしょうか？数学的に難しいことを解き明かすのは凄いんでしょうが、現実世界では更にその続きがあって、そっちの方が大変って事になりませんか？

--
職業としてのプログラマ

Re:

[Led (7726)]

では「P != NP」が証明される事と、素因数分解や離散対数問題がPには含まれず、NPである事とはまた別の問題だと認識していますが違うのでしょうか？

まったく別ではありません。素因数分解や離散対数問題がNPに含まれるのは間違えようがないので^注、もしP=NPであることが示されてしまうと、現在のような利用方法をする暗号はすべて鍵の長さの多項式時間で破られてしまうことになってしまう。そういう意味ではP=NPだったら（暗号分野の人にとっての）理想郷がないことの証明になってしまいます。少なくとも今まで目指していた方向とはまったく別のところに行かなくてはなりません。

ただし、今回の論文が正しくてP!=NPが証明されたとしても素因数分解や離散対数問題の安全性が証明されたことにはなりません。なぜかと

Re:

[Anonymous Coward]

煽りでも何でもなしに

まったく別ではありません。

以降、親コメントの内容と全く同じ話を繰り返している（親コメントを完全に肯定している）ようにしか見えない・・・

Re:

[Led (7726)]

親コメントの

なのでもし「P = NP」が証明されると、現在の公開鍵暗号法式は安全ではなくなる事を意味する。ここまでは理解できます。

を見落としてました。アイタタタ

とりあえず、P!=NPが証明できたら次の仕事はNP完全性の証明ですよ、とだけ付け加えときます。

Re:

[Anonymous Coward]

> とりあえず、P!=NPが証明できたら次の仕事はNP完全性の証明ですよ、とだけ付け加えときます。

これが証明できたなら、量子コンピュータが非決定性チューリングマシンと同等(NP問題を全て多項式時間で解ける)かそれ以上であるということになります。
ただ、そこまでの能力はないと考えられている(NP完全問題を解くことができていない)ため、証明は難しいでしょう。

# 今のところ、素因数分解の判定問題についてはNP完全ではないと考えられています。
# P != NPならば、NPからPとNP完全を除いた集合(NPI)は空集合ではないことも示されているので、そ

Re:P != NP の重要性？

[Led (7726)]

# 今のところ、素因数分解の判定問題についてはNP完全ではないと考えられています。
# P != NPならば、NPからPとNP完全を除いた集合(NPI)は空集合ではないことも示されているので、そこに属していれば安全性は現状維持です。

その通りでした。
手元の教科書を読み返してみたらその通りにかいてありました。