P!=NP 予想、証明されるか ? 53
ストーリー by reo
リーマン予想はまだ検証中でしょうか 部門より
リーマン予想はまだ検証中でしょうか 部門より
ある Anonymous Coward 曰く、
本家 /. 記事によれば、HP Labs の Vinay Deolalikar 氏が P≠NP 予想の証明に関する 100 ページに上る論文の草稿を複数名の様々な分野の研究者に送っており、今週中にも最終稿が公開されるとのこと。
Scribd で公開されている論文は本人のあずかり知らぬところでアップロードされたものらしく、また、Deolalikar 氏は過去にもこの分野の論文をいくつも執筆しているようです。P≠NP 予想は 2000 年にクレイ数学研究所のミレニアム懸賞問題の一つに挙げられており、100 万ドルの懸賞金がかけられています。
タレコミ人は門外漢なので重要そうとしか知りません。この予想それ自体の意味とか、証明の意義とか、コメントお願いします。
S. Cookも一定の評価 (スコア:2, 参考になる)
この予想それ自体の意味とか、証明の意義とか (スコア:2, 参考になる)
ひらたくいうと(つまりかなりいいかげんで正しくない解説)、 「この問題は解候補をしらみつぶしに調べてゆくしかないので厳密解を得るのに時間が掛りすぎるので近似解を求めます」といって厳密解を求めない言い訳が許されてた問題群があります。実は厳密解を求めるのに時間が掛りすぎる(効率よく解くアルゴリズムが存在しない)とは証明されてなかった。 P!=NPだと確定すると、上記の「いいわけ」がいいわけではなくなる。 たとえば巡回セールスマン問題。
Re:この予想それ自体の意味とか、証明の意義とか (スコア:1)
ん? P!=NPだと「効率よく解くアルゴリズムが存在しない」のですから, 言い訳が許されていいのでは?
# 揚げ足取りですみません...
Re:この予想それ自体の意味とか、証明の意義とか (スコア:4, 参考になる)
ちょっとわかりにくいですけど、元コメの主張は「いいわけ」から「反論の余地なし」に昇格するということでしょう。
「実用的な時間で厳密解を求めるのはたぶん無理だから、近似解を求めます」というと
「本当に無理なのか」と聞かれたら答えようのない「いいわけ」になってましたけど
「実用的な時間で厳密解を求めるのは不可能だと証明されているので、近似解を求めます」というと「反論の余地」がありません。
Re:この予想それ自体の意味とか、証明の意義とか (スコア:1, 興味深い)
>「本当に無理なのか」と聞かれたら
私が読んだ教科書には、
「私には解けません」→じゃあクビ、と言われかねない。
「私には解けませんが、世界中の数学者の誰もまだ解けていませんから私が殊更無能なわけではないです」→クビにしても解決しない。
というのが上手いいいわけの例として載ってました。
Re:この予想それ自体の意味とか、証明の意義とか (スコア:1)
Re:この予想それ自体の意味とか、証明の意義とか (スコア:1)
言い訳が許されるのではなく「厳密解を求めるのは馬鹿」と言えるようになるんではないかと.
Re: (スコア:0)
> P!=NPだと確定すると、上記の「いいわけ」がいいわけではなくなる。
ん? P!=NPだと「効率よく解くアルゴリズムが存在しない」のですから, 言い訳が許されていいのでは?
# 揚げ足取りですみません...
「言い訳」では無く、「良い訳」になるのでは？
# 言い訳というと、ちょっと後ろ向きな誤魔化のイメージがありますが
# そうせざるを得ないのだから、近似解が問題に対する「良いアプローチ」になるのだと思います。
Re:この予想それ自体の意味とか、証明の意義とか (スコア:1)
> 「言い訳」では無く、「良い訳」になるのでは？
最初, 言い訳が「良いわけでなくなる」, と読みました。つまり効率よく求められるんだろう? と。
でも, 言い訳が「言い訳でなくなる」, つまり, 正当な理由となる, と読むべきだったんですね。
PvsNP問題で興奮しすぎて, 脊髄反射してしまったようです。
元コメは正しく読めましたね。
すみません。
Re:この予想それ自体の意味とか、証明の意義とか (スコア:1, 参考になる)
巡回セールスマン問題はNP困難だがNP完全ではない(すなわちNPよりもっと難しい)ため、P!=NPの話で持ち出すには不適当、つか全然関係ない。
Re:この予想それ自体の意味とか、証明の意義とか (スコア:1)
Re: (スコア:0)
Re: (スコア:0)
特にsaitoh氏は教育者だということなので、コメを読んで「TSPはNP(完全)」だと思い込む人が出るのはまずい。俺もつられそうになったもん、絶対いるはずだよ。
Re: (スコア:0)
その思い込みはそんなにまずくないと思った次第です。
TSPはNP困難かつNP-easy(日本語の定訳って無いんですかね? NP完全問題に対する効率的なアルゴリズムが存在すれば、同様に効率的に解ける問題のクラス)ですから、
TSPを解く効率的なアルゴリズムが存在する <--> P=NP
が成立しますし。どっちかの矢印が成立しないぐらいに外れた問題なら、全然関係ない、と思いますが。
NPのクラスに関する勉強をするとき以外はそんなに気にしなくても良いんじゃないかと。
ちゃんとした教科書ならどう違うのかの説明から書いてありますから、その段になって誤解のしようはないですし。
あと、論文とか、正式な文章を書くときには書き間違えないよう注意すること。
逆に会話だと、間違って指摘しての応酬が時間の無駄なので、「この問題はNPなので」とかぼかすのがコツ。
Re: (スコア:0)
＿＿＿＿_＿
／＿ |
/. ＼￣￣￣￣|
/ ／ ― ― |
| / - - |
||| (6 > |
| | | ┏━┓| ／￣￣￣￣￣￣￣￣
| | | | ┃─┃| ＜ 正直、すまんかった。
|| | | | ＼ ┃ ┃/ ＼＿＿＿＿＿＿＿＿
| || | | ￣ ￣|
Re: (スコア:0)
その「ちょこっと」が問題の本質にかかわってくるのでダメでしょう。
Re: (スコア:0)
安全な暗号 (スコア:2, おもしろおかしい)
論文を、P!=NPを安全性の根拠にしている暗号でガードしてたのに、多項式アルゴリズムで解読されちゃったせいで流出しちゃったよ、みたいなオチは付きませんか、残念です。
どのくらいすごいかというと (スコア:2, 興味深い)
個人的にはフェルマーの大定理よりインパクト有る
Re:どのくらいすごいかというと (スコア:1, すばらしい洞察)
Re: (スコア:0)
自分は不勉強にして不明だが、確かに勝るとも劣らないぐらい重要に思える。
証明されようが不完全であった事が判明しようが、続報のタレコミ熱望。
Re:どのくらいすごいかというと (スコア:1)
フェルマー予想はもし否定されてしまったら他に与える影響が甚大だったそうだ。(自殺する数学者が出かねないと読んだことがある)
P≠NP はそこまで行ってないようだ。
the.ACount
Re:どのくらいすごいかというと (スコア:3, 興味深い)
P=NPならオンラインコマースは壊滅ですよ? (安全な一方向関数を作ることが原理的に不可能)
フェルマー予想ごとき比較にならないほど影響が大きいと思いますが。肯定的に証明されるならそれほどインパクトはないでしょうけど。
Re:どのくらいすごいかというと (スコア:1)
今世紀中に量子計算機ができるから、それまでさ。
the.ACount
Re: (スコア:0)
Re: (スコア:0)
ミレニアム懸賞問題の中ではフェルマーの大定理と同じぐらい、問題の意味を説明するのは容易いと思った。
#他は高等すぎて、題意すら分からない。
Re:どのくらいすごいかというと (スコア:1)
リーマン予想は高校数学で理解できる（と、参考書に書いてあったような気がする）。
＃解けるわけじゃない。
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完全だとすると，確かこれらを多項式時間で解ける量子コンピュータの計算能力がどーなんだって話がありますね．
MIT 研究者 「もし証明が正しければ 私も【約２千万円】を寄贈する」 (スコア:1, 興味深い)
と確言してますが、 これは 「証明は確実に間違っている」 という意味ですよね？
http://scottaaronson.com/blog/?p=456 [scottaaronson.com]
If Vinay Deolalikar is awarded the $1,000,000 Clay Millennium Prize for his proof of P≠NP, then I, Scott Aaronson, will personally supplement his prize by the amount of $200,000.
Re: (スコア:0)
（コメント欄でも、何人かが nasty、Crass、…と言ってる） http://scottaaronson.com/blog/?p=456 [scottaaronson.com] >>> Betting against a colleague is nasty,
２０万円、２００万円なら、まだ本気かもしれんと思うが、【約２千万円】というのは 「もちろん冗談だった」という逃げ道を想定しての事だろうな。
日本にも川崎和男という卑劣なBlogger
タイトルがおかしくないですか？ (スコア:0, オフトピック)
「P!=NP」と「P≠NP」は同じじゃないですよね？
Re:タイトルがおかしくないですか？ (スコア:1)
Re:タイトルがおかしくないですか？ (スコア:2, 興味深い)
でもまあ、
(P!) = (NP)
#Pの階乗がNPに等しい。
と読むか
(P) != (NP)
#PはNPと等しくない
と読むかで
意味は違ってくるような。
いや、そんな！ あの毛は何だ！ 枕に！ 枕に！
Re:タイトルがおかしくないですか？ (スコア:2, おもしろおかしい)
Re: (スコア:0)
Re: (スコア:0)
Re: (スコア:0)
あらー。
同じか。
すいません。
# genkikkoですが沈むようにACで。
Re: (スコア:0, オフトピック)
本文中の記載とタイトルでの記載には統一性があった方がよろしいですよね。申し訳ない。
# でもまあ同じだからいいじゃん、というご指摘もあるので今回はこのまま。
Hiroki (REO) Kashiwazaki
リーマン予想関連かな？ (スコア:0)
1+2+3+4+… [wikipedia.org]
= -1/12
これを見て解析接続を理解することを断念した私は、しがないサラリーマンです。
残念っ！ (スコア:0, おもしろおかしい)
P=NP問題は既に解決しています。しかも日本人の手によって！
本まで出ています [int2.info]
もうちょっと早ければ良かったのにね～。惜しかったね。
Re: (スコア:0)
リンク踏んだら
なんの関係も無い表記ゆれの酷い丁寧語の怪しい駄文を見せつけられてｳﾎﾞｱｰ('A`)な気分になった。
イントロのレベルで既に胡散臭いんだけどマジなの？
Re:残念っ！ (スコア:1, 興味深い)
著者名でぐぐるとどんな人かわかります。興味があればどうぞ。
「できた！」思い込んで実は間違いだった人が続出だったのか、著名な論文誌であるJournal of the ACMあたりでは「P/NPに関する論文は一人あたり２４ヶ月に一本しか受け付けません」と宣言しています [acm.org]。