ノート:P≠NP予想

まだ論文を投稿した段階のようなので、解決したことが知られている、とまで書くのは明らかに書き過ぎかと。またこの手の話は良くあることなので、正式に解決が宣言されるか、大々的にメディアで取り上げられたりするまでは待った方が賢明でしょう。出でやる 10:13 2003年8月8日 (UTC)

• Wikipediaの目的はWikipedia:ウィキペディアは何でないかを読むとはっきりします。そこには「ウィキペディアでは、人類の知識となっているものを編纂しています。まだ人類共通の知識となっていない意見を伝達する場所ではありません。」とあります。難問を解決したと主張する人は角の三等分をはじめ無数におります。山口氏の証明の内容を示したWebサイトのURLを参照する程度にとどめておいてはいかがでしょうか。P≠NP予想とは無関係な個人の行動をエッセイのように書いても百科事典にはならないと思いますが。---Redattore 2005年11月10日 (木) 15:11 (UTC)

査読のある雑誌で解決したと認められるか、あるいは認められつつある状態になった段階で書けば十分だと思われるのでrevertしました。--mochi 2005年11月10日 (木) 15:21 (UTC)

私の提案は甘すぎました。怪しい証明を示したURLが山のように付くことも考えられますね。---Redattore 2005年11月10日 (木) 15:27 (UTC)

保護中の修正

{{sci-stub}}の上に何故か「z」が入っている、という指摘がありましたので除去しました。 -- ＮｉＫｅ 2006年8月5日 (土) 02:08 (UTC)

要出典

本記事の下記の一文に[要出典]テンプレートを貼り付けました。

現在の暗号、特に共通鍵暗号方式は、鍵無しで暗号文から平文に戻す非線形方程式を作成すると、その方程式を解くことは少なくともNP完全問題を解く以上に難しいことを証明することで、「安全」と見なされている[要出典]。

明らかな間違いのような気もします。でも何かを参考に執筆されたならば、元のテキストを確認した上で編集したいと思いました。出典をご存知の方、お願い致します。Sina 2006年11月11日 (土) 04:38 (UTC)

その文を追加した者です。その文章の出展は

アルト・サロマー、『公開鍵暗号系』、足立暁生訳、東京電機大学出版局、1992、ISBN 4-501-51840-5

という書籍からです。この書籍は最初の章で共通鍵暗号について解説しているのですが。その章の最後の方に

「暗号解析は尤大な数の非線形問題を解くことになるが、そこで解かなければならない問題は少なくともNP完全である。」

と書かれた文があったからです。ただ書籍を改めて読むとDESにのみかかっているようにも読めるのと、明確な証拠となる出典を引用していないため、もしかしたら著者の誤認かもと感じていた部分で、僕自身も近々大幅に変更する予定でした。なのでその部分を変更ないし削除には賛成します。--U-ichi 2006年11月14日 (火) 05:56 (UTC)一部修正しました。--U-ichi 2006年11月14日 (火) 07:43 (UTC)

お返事ありがとうございます。69ページの一番下3行ですね。前後の流れからして、「DESはアルゴリズムを完全公開した画期的な暗号方式であるが、その解読は大変である。仮に、平文・暗号文ペアを入手して鍵を未知の変数とする方程式を立てて、この方程式を解くことで暗号解読を行うアプローチをした場合には、NP完全問題（NP困難？）よりも大変である」ということを指摘したいように読めました。色々疑問を感じます。共通鍵ブロック暗号で証明可能安全性という考え方がありますが、暗号の安全性を評価する場合には、解読と同等な意味を持つ方程式を立てて、それが容易には解けないことを示すというようなアプローチでは考えていないと思います。（どちらかというとNP完全問題に多項式時間帰着が示せると、暗号方式としてどこかで破綻している気も・・・）。ただ、PvsNP問題が暗号理論にとって極めて影響が大きく重要な問題であること自体は間違いないと思いますので、適当な表現に推敲されるとよいと思います。近々編集のご予定あるようでしたお任せいたします。Sina 2006年11月14日 (火) 14:24 (UTC)

疑問

現在の版は少し前の 2006年12月2日 (土) 09:43 Lem の版と比べて、不正確な記述になっていないでしょうか。例として次の2文を挙げます：（前者は単にTYPO？、後者は前の文との繋がりが不適切）

• 端的な言い方をすると「計算はできても検算はできない問題が存在する」ということになる。
• P≠NPが証明されるならば、一方向性関数の存在と公開鍵暗号の安全性も証明されることになる。

この2点に限らず、全体的に前の版の方がずっと望ましいように思い、元に戻そうと考えています。その際に、

• 同研究所はこの問題を含めて7つの未解決問題の証明に100万ドルの賞金をかけているが、この問題だけが計算機科学と重なる分野からの問題である。

などの削除された幾つかの文章について、これらは不適当な記述であり復活させない方がよいものかどうか、この分野に詳しい方にコメント頂けないできないでしょうか？ Sina 2007年1月14日 (日) 15:41 (UTC)

他の問題が計算機科学と重ならないことは原理的に検証不能なので、「この問題だけが」は不適切でしょう。Wd 2007年1月16日 (火) 07:38 (UTC)

それは確かにそうかも知れません。「この問題だけが、...重なる分野」を除いて、単に「この問題は、ミレニアム懸賞問題の7つのうちの一つに挙げられている」程度の記述が適当でしょうか。ご意見ありがとうございます。もう暫く待って他にご意見がなければリバート＆上記の編集をします。Sina 2007年1月17日 (水) 14:30 (UTC)

Sinaさんが疑問を感じていることはわかりました。しかし、なぜ疑問を感じているのかがよくわかりません。正確性（前は正確だったけど、新しいのは不正確）の問題ですか？それとも前の方がわかりやすかったということですか？

• 前者はどういうTYPOだと考えているんでしょう？
• 後者について。文のつながりということでいえば、もう一つ前の「一方向性関数は、P≠NPが前提となる」という記述を受けてこの文が記述されています。直前の文は、「例示」によってその前の文を補足説明しています。j8takagi 2007年1月17日 (水) 15:33 (UTC)

「単にTYPO？」と決めつけてしまうのは失礼なことだったかもしれません。1番目については、「検算はできない問題が存在する」という部分を取り出すとよく分ると思います。「検算できない問題」とはクラスNPに属さない問題のことではないでしょうか？ つまり、P vs. NP とは関係ない言明になってしまっています。2番目については、色々な点で不適切に感じますが、その一つとしてIFPやDLPがNP困難に属するかのような説明になっている点があります。これはまだ真偽不明なのではないでしょうか。この記述をサポートするような出典をご存知でしたら提示して頂けますか？要出典とUnreferencedを添付してもよろしいでしょうか？Sina 2007年1月18日 (木) 17:10 (UTC)

1番目について。

1. ｛「検算できない問題」とはクラスNPに属さない問題のことではないでしょうか｝というのが意味がよくわからないので、説明をお願いします。
2. ｛「検算できない問題」とはクラスNPに属さない問題｝なので｛P vs. NP とは関係ない言明になってしまっている｝というSinaさんご指摘の問題は、言明「検算可能な問題は全て計算可能であるか、可能でないか」（2006年12月2日 (土) 18:43版）では発生しなくて、言明「計算はできても検算はできない問題が存在する」では発生するんでしょうか？

2番目について。
読者の多くが「IFPやDLPがNP困難に属するかのような説明になっている」ような解釈をするということであれば、文章の書き方がまずいんでしょうね。書き手の意図は、（前にも述べたように）素因数分解と離散対数問題について触れた文は、「例示」によってその前の文を補足説明しているということです。
ところで、IFPやDLPってinteger factorization problemすなわち素因数分解とdiscrete logarithm problemすなわち離散対数問題のことですよね。言い換えるのに何か意味があるんですか？

要出典について
不適切な行動ではないかと考えます。今回の件は、「記述の整理」が適切かどうかが論点で、出典とは関係ない話です。例えば、元の記述とまったく異なる内容になってしまったとか、新たに誤った記述を追加してしまったとか、かえってわかりにくくなったとかいうことであれば、編集は不適切だったと判断して前の版に戻すというのが妥当でしょう。ただしSinaさんのいままでのご発言では、「記述の整理」が適切ではなかったという十分な説明にはなっていないと思います。上記1番目の2について多くの人が納得できるようなお考えを表明いただけるなら、その点については十分な説明があったといえるでしょうが。j8takagi 2007年1月19日 (金) 16:43 (UTC)

横から失礼します。たぶん整理前の記事を一番執筆していたのは僕なので意見を言わせてもらいます。

とりあえず 1番目については j8takagiさんには悪いですが完全に意味を間違えています。P≠NP予想は「計算はできても検算はできない問題が存在する」ではありません。というか計算できる（Pである）問題は全て検算ができる（NPである）問題です（それを示すために P ⊂ NP云々の記述を整理前の文章に置いていました）。意味が完全に逆です。「答えの検算ができても、答えを計算することができない問題が存在する」なら正しいです。

2番目のことについては正直自分で書いた記事なのでどちらが分かり易いかは判断しかねます。ただ「P≠NPと証明されたら、RSA や Elgamal の安全性が証明できる」ととられる文章になってしまっているかなと感じます（たとえ P≠NP が証明されても、解るのはあくまで一方向関数が存在するということだけであり、素因数分解や離散対数問題が一方向性関数かどうかに関してはわかりません）。

いずれにせよ整理前の僕の記述が良くなかったのが原因ともいえるのでその点はお詫びします。

追記：最初に Sina さんが戻すかどうかを提案された「この問題だけが計算機科学～」という記述は、僕がこの問題が情報工学の分野との関わりが深いことを示したくて「情報工学と重なる」と書いたのを Wd さんに「情報科学」に変えられて、ただその当時情報科学は情報学のリダイレクトで不適切だったため CESさんに「計算機科学」に変えられたという経緯があります。そのため計算機科学は広義では数学の一種になるので Wd さんの言われたとおり検証不可能になってしまいました。というのが実情です。僕も残したままにしておくかどうか判断に迷っていた部分なのでこの文章を戻すのは控えた方が無難かと思います。一応言い訳として…--U-ichi 2007年1月19日 (金) 18:08 (UTC)

U-ichiさんのご意見、了解しました。本文の記事を修正したので、ご確認ください。j8takagi 2007年1月20日 (土) 02:06 (UTC)

U-ichiさん、ご意見ありがとうございます。「検算できない問題はNPには属さない問題のことでは・・・」について「意味がよくわからない」とおっしゃる方に何を説明したらよいのかと悩んでいました。j8takagiさん、1番目と2番目の点について修正はされていますが、それでも元の版の方が望ましい説明と思います。元の文章では、

• 逆にいえば P≠NP と証明できるなら、「一方向性関数は存在する」ことになり少なくとも多項式時間では破れない暗号が存在することの証明になる。

でしたが、ここも「暗号が存在することの証明になる」と「公開鍵暗号の安全性も証明される」では意味が違います（後者では間違い）。編集を継続されているようなので、しばらくリバートするのは保留します。少なくとも元の版よりは望ましい状態になるのを期待してます。Sina 2007年1月20日 (土) 02:26 (UTC)

「ノートでのご指摘を反映」との要約で編集されていましたので、見てみましたら「一方向性関数の存在は、P≠NPが証明されるならば、証明される。」と単純に削除された状態になっていました。このような状態にするぐらいなら、一時的であれ元々の版に戻したほうがよいと思います。Sina 2007年1月20日 (土) 05:40 (UTC)

Sinaさんの{「公開鍵暗号の安全性も証明される」では意味が違います（後者では間違い）｝というのは、「公開鍵暗号の安全性も証明される」は間違えているというご指摘ではありませんか？間違えといえるかの確信はありませんが、正しいという確信も持てないので削除したということです。この編集がSinaさんの意に沿わないというのは仕方ないとは思いますし、この編集以外によりよい方法があったかもしれないとは思います。しかし、そのことと「元々の版に戻したほうがよい」という主張には論理の飛躍があります。Sinaさんは、記事をよいものにする（そのための議論をする）というよりも、編集は差し戻すべきである（そのための根拠と手続きを議論する）、ということを先に考えているようにも思います。j8takagi 2007年1月20日 (土) 08:43 (UTC)

「元々の版に戻したほうがよい」のは、元々の表現ならば間違いではなかったからです。編集が不適切な場合には元に戻すというのはj8takagiさんにも同意頂けるのではないでしょうか。元々あった文章を弄んで最後は削除というのでは、あまりにボロボロです。「今の版をよいものにしましょう」と呼びかけられても、Sinaは躊躇してしまいます。他の方々はそうでもないのでしょうか。Sina 2007年1月20日 (土) 11:06 (UTC)

では、ほかの方の意見を聞くということにしましょう。j8takagi 2007年1月20日 (土) 11:09 (UTC)

それはそれは。。。1～2週間くらいはお待ちするのがよろしいのでしょうか。それで今の版と変らない状態でしたら、元々の版をベースに（j8takagiさんのご編集であっても妥当だと思われるところは採用して）編集を行いますね。Sina 2007年1月20日 (土) 13:07 (UTC)

2週間近く待ちましたが（TYPOの修正を除いて）今の版への加筆・推敲は行われませんでした。それで、元々の版をベースにした編集を開始します。おかしなところがありましたら修正やご指摘をお願い致します。

それと、Wikipedia:コメント依頼/Sinaにて、「他のユーザーをなじるような論調」があるとのことでj8takagiさんがコメント依頼を出しています。本ノートでのSinaの書き込みに不適切なところがあると感じられた方は、是非コメントをお願い致します。Sina 2007年2月2日 (金) 15:04 (UTC)