パスワードを忘れた? アカウント作成
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

arxiv に P≠NP 問題を解決した論文が投稿される」記事へのコメント

  • P=NP のほうが色々と役立つし

    • by Anonymous Coward on 2017年08月16日 21時00分 (#3262200)

      もう20年来、否定の予想で専門家の間では定着しているから、
      今さら肯定的結論では、そちらの方が大混乱だよ。
      セキュリティ関連への悪影響と最適化問題への有用性だと、今はもう
      悪影響の方が大きいんじゃないかな。

      親コメント
      • 商用化へ加速、量子コンピューター「9000兆倍の破壊力」 [nikkei.com]
        あたりを見ると、だいぶ盛っているにしても稼動するようになってから一般に使えるようになるまでの間は数理的な証明如何に寄らず「量子コンピュータを使える組織にとっては暗号は解ける物」って状態が不可避に思えますね。
        # 暗号方式と運用で何とかなる方法、あるのかな。。。

        親コメント
        • by Anonymous Coward

          量子アニーリング式と量子ゲート式の区別すらついてないクソ記事なんぞ読むにも値しない

      • by Anonymous Coward

        (肯定的に)証明できても、解が直ちにわかるわけじゃないから、どうってことない気もするが。

        • by Anonymous Coward

          自分の名前をパスワードにしても直ちに破られる訳ではないから
          どうってことないと言っているほどに、おめでたい。

          • by Anonymous Coward on 2017年08月17日 10時56分 (#3262418)

            そうでもないんだ。数学の歴史を紐解くと酷い事例が結構ある。

            数学者A「○○できる方法が存在することを証明しました」←この証明はちょっと基礎知識があれば簡単に理解出来る
            数学者A「え? その方法の実例? 存在するとは言ったけど具体的なやり方は知らんがな」

            -長い年月-

            数学者Z「ついにそのアルゴリズムの実例を見つけました!」←とてもじゃないけど理解不能

            数学者Aのその発見から新たな分野ができあがり、そんな考え方もあるのか、
            いっちょやったろかと突っ込んでった無数の数学者が死屍累々した後で、ようやく解決するというパターン。
            ああいう天才は天才なので、一番美味しい所だけちょこっと持って行って放置しよる、と先輩が泣いてた。

            有名どころでは、シャノンの通信路符号化定理 [wikipedia.org]とか。

            親コメント
            • by Anonymous Coward

              こちらのほうが長いから、こっちに返事つけますが、
              具体的アルゴリズムが得られてないってのは、P=NPがわかっているのに比べて
              はるかに時間の問題だと思うのだけど。
              まさにパスワードと生年月日の問題くらいに。
              具体的アルゴリズムの多項式の次数が高いってのは、お話にならないくらい本質的に
              時間の問題だよな。

              純粋数学と違って対象のつかみどころは割りとはっきりしているから、
              P=NPの証明ができたら、アルゴリズムに関する知見もかなりあると見るのが妥当。
              もしくは、P=NPどころではない何かすごいものを見つけて証明しているかになる。
              その場合は、まあ、私の言っていることは外れることになるけど、そのときは
              こんな議論どうでもよいほど面白い世界に変わるから、私はそっちにいく。

              • by Anonymous Coward

                うん、まあ、証明されるとしたら、その「P=NPどころではない何かすごいもの」方面になると思うんだ。
                さくさく実用出来るようなアルゴリズムが実在するようなら、もう既にP=NPは証明されてるだろうし。

                SFネタとしてはさくさく暗号解読できるアルゴリズムが見つかる方が好きだけどね。

              • by Anonymous Coward

                存在証明はされているけど具体的な特定は不可能って数学ではよくあるから
                "時間の問題"で片付くほど簡単には思えないけどな。
                それにもし手続きが見つかったとしても、O(n^グラハム数)とかでしょどうせ。
                素数判定のO(n^7.5)ですら実用にならんしそうそう都合良くはいかない。(面白い世界になってほしいというのは同意だが)

            • by Anonymous Coward

              ちなみにシャノン限界は、計算量理論だと計算時間の下界と同じようなもんで、
              下界の計算時間のアルゴリズムを見つける=タイトバウンドを見つけるのは
              難しい問題。
              P=NPの場合は、それ自身がタイトバウンドを見つけたイメージになる。

          • by Anonymous Coward

            話の本質が分かってないね。

          • by Anonymous Coward

            P=NPであることと、NP問題を多項式時間で解く方法が具体的に得られることと、そのアルゴリズムが現実的なレベルのオーダーであることは全部別だよね

          • by Anonymous Coward

            P=NPは決定問題なので、直ぐに何かが起こるという結論の間には実は、ギャップがある。

            P=NPである、というのは、おなじみの巡回セールスマン問題で言うと、「全長x未満の経路はある?」にYes/Noの解を求めるアルゴリズムが存在する、と言う意味。直ぐに分かることとして、2分探索をすれば、「最短の経路長は?」という問題も解ける。

            ただ、「最短の経路を求めよ」という問題はまた別。

            「もしも」の話をするなら、「P=NP」が証明された上で、「最短の経路を求めよ」の方は多項式オーダーでは解けないと証明される、という超展開もあり得る。

            「P!=NP」→「最適化問題問題の方も解けない」、とか、「最適化問題が解けた」→「P=NP」とかは真なので、「どうせP!=NPなんだからそこまで深く考えなくても」とスルーされがちだけど。

日本発のオープンソースソフトウェアは42件 -- ある官僚

処理中...