アカウント名:
パスワード:
では「P != NP」が証明される事と、素因数分解や離散対数問題がPには含まれず、NPである事とはまた別の問題だと認識していますが違うのでしょうか？
まったく別ではありません。素因数分解や離散対数問題がNPに含まれるのは間違えようがないので注、もしP=NPであることが示されてしまうと、現在のような利用方法をする暗号はすべて鍵の長さの多項式時間で破られてしまうことになってしまう。そういう意味ではP=NPだったら（暗号分野の人にとっての）理想郷がないことの証明になってしまいます。少なくとも今まで目指していた方向とはまったく別のところに行かなくてはなりません。
ただし、今回の論文が正しくてP!=NPが証明されたとしても素因数分解や離散対数問題の安全性が証明されたことにはなりません。なぜかというと素因数分解や離散対数問題がクラスNPの中の難しい問題（NP完全）なのかどうかもよくわかってないからです。（私のフォローしている限りではまだわかってないことになっています。）理想郷にいるかどうかはまだ確定ではないが、今まで目指してきた方向付近に理想郷があることが証明されるといったところでしょうか。
現実世界では更にその続きがあって、そっちの方が大変って事になりませんか？
実用化されている暗号を破る問題がNP完全であることを証明すれば、自分たちが理想郷にいることが確定します。P!=NPが証明できれば大きな一歩には間違いありません。ただし、今までの仕事とこれからの仕事のどっちが大変かは誰も知りません。
注：答えを与えられればその検証が多項式時間でできる問題はすべてNPに入る問題です。したがって、鍵があればすぐに復号できる暗号を破る問題はすべてNPに入ります。
まったく別ではありません。
以降、親コメントの内容と全く同じ話を繰り返している（親コメントを完全に肯定している）ようにしか見えない・・・
親コメントの
なのでもし「P = NP」が証明されると、現在の公開鍵暗号法式は安全ではなくなる事を意味する。ここまでは理解できます。
を見落としてました。アイタタタ
とりあえず、P!=NPが証明できたら次の仕事はNP完全性の証明ですよ、とだけ付け加えときます。
Indian-origin scientist's math proof has 'serious loopholes'http://sify.com/news/indian-origin-scientist-s-math-proof-has-serious- [sify.com]...インド出身科学者の数学証明には"重大な穴"がある。という記事。
検証作業は進んでいるようです。
わたしなんぞのコメントよりもこの親コメントに「参考になる」を進呈したいですね。
> とりあえず、P!=NPが証明できたら次の仕事はNP完全性の証明ですよ、とだけ付け加えときます。
これが証明できたなら、量子コンピュータが非決定性チューリングマシンと同等(NP問題を全て多項式時間で解ける)かそれ以上であるということになります。ただ、そこまでの能力はないと考えられている(NP完全問題を解くことができていない)ため、証明は難しいでしょう。
# 今のところ、素因数分解の判定問題についてはNP完全ではないと考えられています。# P != NPならば、NPからPとNP完全を除いた集合(NPI)は空集合ではないことも示されているので、そこに属していれば安全性は現状維持です。# ただし、この証明はP != NPを証明することを含んでいるため、現状は難しいですが。
あと、量子コンピュータが決定性チューリングマシンに当てはまらないというわけではありませんね。正しくは、決定性チューリングマシンと同等か、それ以上です(量子コンピュータは決定性チューリングマシンを模倣できるので)。現状、P != NPは証明されていないため、それ以上の能力を持っているかは不明です。
# 今のところ、素因数分解の判定問題についてはNP完全ではないと考えられています。# P != NPならば、NPからPとNP完全を除いた集合(NPI)は空集合ではないことも示されているので、そこに属していれば安全性は現状維持です。
その通りでした。手元の教科書を読み返してみたらその通りにかいてありました。
別にNP完全じゃなくても，(P != NPなら)Pに属さなければいいのでは？
あと，素因数分解や離散対数問題がNP完全だとすると，確かこれらを多項式時間で解ける量子コンピュータの計算能力がどーなんだって話がありますね．
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
Stableって古いって意味だっけ？ -- Debian初級
P != NP の重要性？ (スコア:1)
Wikipediaにもあるように、現在の公開鍵暗号法式は「P != NP」が前提で、確認できていないが素因数分解や離散対数問題はPには含まれない事を頼りにしていると理解しています。
なのでもし「P = NP」が証明されると、現在の公開鍵暗号法式は安全ではなくなる事を意味する。ここまでは理解できます。
では「P != NP」が証明される事と、素因数分解や離散対数問題がPには含まれず、NPである事とはまた別の問題だと認識していますが違うのでしょうか？
つまり「P != NP」を証明しても、現状の「素因数分解って簡単にはでけへんと思うは、そうやろ？だからきっと安全やで」の世界からは一歩も前進していない。 理想郷はあるらしいが、ここがそうかは誰も知らずに幸せに暮らしているのと変わらないんじゃ無いんでしょうか？数学的に難しいことを解き明かすのは凄いんでしょうが、現実世界では更にその続きがあって、そっちの方が大変って事になりませんか？
職業としてのプログラマ
Re:P != NP の重要性？ (スコア:3, 参考になる)
では「P != NP」が証明される事と、素因数分解や離散対数問題がPには含まれず、NPである事とはまた別の問題だと認識していますが違うのでしょうか？
まったく別ではありません。素因数分解や離散対数問題がNPに含まれるのは間違えようがないので注、もしP=NPであることが示されてしまうと、現在のような利用方法をする暗号はすべて鍵の長さの多項式時間で破られてしまうことになってしまう。そういう意味ではP=NPだったら（暗号分野の人にとっての）理想郷がないことの証明になってしまいます。少なくとも今まで目指していた方向とはまったく別のところに行かなくてはなりません。
ただし、今回の論文が正しくてP!=NPが証明されたとしても素因数分解や離散対数問題の安全性が証明されたことにはなりません。なぜかというと素因数分解や離散対数問題がクラスNPの中の難しい問題（NP完全）なのかどうかもよくわかってないからです。（私のフォローしている限りではまだわかってないことになっています。）理想郷にいるかどうかはまだ確定ではないが、今まで目指してきた方向付近に理想郷があることが証明されるといったところでしょうか。
現実世界では更にその続きがあって、そっちの方が大変って事になりませんか？
実用化されている暗号を破る問題がNP完全であることを証明すれば、自分たちが理想郷にいることが確定します。P!=NPが証明できれば大きな一歩には間違いありません。ただし、今までの仕事とこれからの仕事のどっちが大変かは誰も知りません。
注：答えを与えられればその検証が多項式時間でできる問題はすべてNPに入る問題です。したがって、鍵があればすぐに復号できる暗号を破る問題はすべてNPに入ります。
Re: (スコア:0)
まったく別ではありません。
以降、親コメントの内容と全く同じ話を繰り返している（親コメントを完全に肯定している）ようにしか見えない・・・
Re:P != NP の重要性？ (スコア:1)
親コメントの
なのでもし「P = NP」が証明されると、現在の公開鍵暗号法式は安全ではなくなる事を意味する。ここまでは理解できます。
を見落としてました。アイタタタ
とりあえず、P!=NPが証明できたら次の仕事はNP完全性の証明ですよ、とだけ付け加えときます。
Re:P != NP の重要性？ (スコア:1, 参考になる)
http://sify.com/news/indian-origin-scientist-s-math-proof-has-serious-... [sify.com]
インド出身科学者の数学証明には"重大な穴"がある。という記事。
検証作業は進んでいるようです。
Re:P != NP の重要性？ (スコア:1)
Indian-origin scientist's math proof has 'serious loopholes'
http://sify.com/news/indian-origin-scientist-s-math-proof-has-serious- [sify.com]...
インド出身科学者の数学証明には"重大な穴"がある。という記事。
検証作業は進んでいるようです。
わたしなんぞのコメントよりもこの親コメントに「参考になる」を進呈したいですね。
Re:P != NP の重要性？ (スコア:1, 参考になる)
> とりあえず、P!=NPが証明できたら次の仕事はNP完全性の証明ですよ、とだけ付け加えときます。
これが証明できたなら、量子コンピュータが非決定性チューリングマシンと同等(NP問題を全て多項式時間で解ける)かそれ以上であるということになります。
ただ、そこまでの能力はないと考えられている(NP完全問題を解くことができていない)ため、証明は難しいでしょう。
# 今のところ、素因数分解の判定問題についてはNP完全ではないと考えられています。
# P != NPならば、NPからPとNP完全を除いた集合(NPI)は空集合ではないことも示されているので、そこに属していれば安全性は現状維持です。
# ただし、この証明はP != NPを証明することを含んでいるため、現状は難しいですが。
あと、量子コンピュータが決定性チューリングマシンに当てはまらないというわけではありませんね。
正しくは、決定性チューリングマシンと同等か、それ以上です(量子コンピュータは決定性チューリングマシンを模倣できるので)。
現状、P != NPは証明されていないため、それ以上の能力を持っているかは不明です。
Re:P != NP の重要性？ (スコア:1)
# 今のところ、素因数分解の判定問題についてはNP完全ではないと考えられています。
# P != NPならば、NPからPとNP完全を除いた集合(NPI)は空集合ではないことも示されているので、そこに属していれば安全性は現状維持です。
その通りでした。
手元の教科書を読み返してみたらその通りにかいてありました。
Re: (スコア:0)
別にNP完全じゃなくても，(P != NPなら)Pに属さなければいいのでは？
あと，素因数分解や離散対数問題がNP完全だとすると，確かこれらを多項式時間で解ける量子コンピュータの計算能力がどーなんだって話がありますね．