パスワードを忘れた? アカウント作成
13381181 story
数学

arxiv に P≠NP 問題を解決した論文が投稿される 52

ストーリー by hylom
検証を待て 部門より
fromage曰く、

計算機科学の未解決問題であるP≠NP予想を解決したとする論文がarxivに投稿された(結城浩氏のツイート論文のページ)。

NP完全問題は、巡回セールスマン問題のような、入力(重み付きグラフと閾値)に対する証拠(巡回経路)があれば入力を多項式時間で判定できる問題の中では最も難しいものである。NP完全問題を多項式時間で解くアルゴリズムはまだ見つかっていない。そのようなアルゴリズムが存在すればP=NPであり、存在しないならばP≠NPであるが、現在までどちらなのか分かっていない。

今回投稿された論文では、P≠NP(つまり、NP完全問題は多項式時間で解けない)と結論付けている。著者が計算機科学の専門家(大学の情報科学科の教授)である点から、この論文に期待する意見もある。しかし、arxivには査読の仕組みがないため、この証明が正しいかどうかは、現段階では不明である。

ところで、P≠NP問題を解決したと主張する論文のリストを示しているページによると、(査読を通ったものを含めて)116本の論文がこれまで発表されている。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • by Anonymous Coward on 2017年08月16日 22時58分 (#3262271)

    理論計算機科学の専門家(カリフォルニア大学バークレイ校の教授)が、この論文の背景となっているこれまでの(回路計算量の)研究の流れと、この論文の主張の概要について、ブログで解説しています [wordpress.com]。ただ、「既存研究にはない新しい手法が導入されたことで問題が解決された」わけではないと捉えていて、この論文の正しさには懐疑的なようです。

  • by Anonymous Coward on 2017年08月16日 20時32分 (#3262194)

    なんでこの論文が注目されてるの?
    見込みがあるのでしょうか。

    • by Anonymous Coward

      スラドにたれこまれた理由は、奥村センセがtweetしたから。

  • この論文が検証されている中で、間違いの具体的な指摘が2つ出てきました。
    (1) 論文の中で基盤となっている定理を示した研究者である Alexander Razborov 教授が、論文中の矛盾を指摘しました(Razborov 教授の知人による投稿 [stackexchange.com], それを紹介している山形頼之氏のツイート [twitter.com])。
    今回の論文が参考にしている先行研究である Berg and Ulfberg による議論(単調回路に対する下界を示すのに CNF, DNF の両方を使う方法)は Tardos の関数についても成り立つが、それは今回の論文の定理 6 と矛盾するので、この論文は必然的に間違いになる、と説明されています。
    (2) 今回の論文の定理 6 の証明における帰納法に誤りがある(詳細 [stackexchange.com]、 山形頼之氏のもう1つのツイート [twitter.com])とのことです。
  • by Anonymous Coward on 2017年08月16日 18時57分 (#3262131)

    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 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なんだからそこまで深く考えなくても」とスルーされがちだけど。

    • by Anonymous Coward

      査読なしだと、エイプリルフール的なネタ論文の可能性もある。

      多分そうじゃないの?本気で正しいと思ってるなら、査読付きで権威のある論文誌に投稿すんでしょ。
      #「再昇華チオチモリンの吸時性」を読み返したくなった。

      • by Anonymous Coward

        > 査読付きで権威のある論文誌に投稿すんでしょ。
        たまに変人がいるみたい

        https://ja.wikipedia.org/wiki/ArXiv#.E3.83.9D.E3.82.A2.E3.83.B3.E3.82.... [wikipedia.org]

        • by Anonymous Coward

          そんな奇人変人列伝の一人に挙げられそうな例を出されても…
          # しかし得てして天才数学者は変人だから困る

          • by Anonymous Coward

            まあ、せっかく公開されている論文を自分でチェックできるような知力がなくて、周辺であれこれ言ってる程度なら黙って専門家の判断を待ってるのが吉ですね。

      • by Anonymous Coward

        体裁を整えるには大変な手間がかかるし査読も数年かかることがあるからとりあえずarXivに投稿するのは不思議ではない

      • by Anonymous Coward

        ちなみに "The P-versus-NP page" には査読付きの論文もあるので査読は意外とあてにならないらしい

        • by Anonymous Coward

          らしいってーか「無いよりマシ」程度なのはみんな分かってるよ。
          それでも「無いトコのは眉に余計にツバつけとけ」って評価は変わらない。

      • by Anonymous Coward

        数学とか計算機科学の論文は記号論理学的な記述にコンパイル可能なフォーマットで提出を義務付ければ定理検証は容易にできるはずだからそういう形になればいいのに。
        AIによる機械学習にも使えるし、在野の自称数学家でも普通に提出できるし。

        査読なんて社会学的で不確かな手法は時代遅れになるべきだ。

    • SSL(の秘匿性を前提とした電子商取引)やブロックチェーンは死亡だしNSAや中国やロシアは大歓喜だしね。

      • by Anonymous Coward

        いやいやあらゆる数学の証明がパソコンを数時間とか(+-数十桁)回せば自動で可能になるだけで大きな魅力だと思わないか?
        アルゴリズムも解の満たす条件を記述するだけで十二分になるんだよ。TASとかも超簡単。

        暗号化なんてのは量子暗号やワンタイムパッドが全てを解決するよ多分。

        • by Anonymous Coward

          通りすがりコメですが、

          もしも、
          解決したら、その関係者達が知れ渡ったら、某競馬場やラスベガスとかでヤサグレている方々の視線が飛んできそうですね。
          そしてその歴史的瞬間をTV視聴してみたいと思います。

          • by Anonymous Coward

            P=NPが証明されてからの顛末を小説にしたら絶対楽しいだろうなと思ったけど、そんな小説はすでにあるらしい。
            これ [amazon.co.jp]。
            読んだ事はないけど、とにかくすごく楽しい事が起きるのは間違いないと思う。暗号の崩壊を含めてね。

            • by Anonymous Coward

              それ、amazon のアフィリエイトつきリンクでは。意図的にやっているならやめてほしいし(amazon アフィリエイトの規約違反)、ミスなら気を付けてほしい。

              • by Anonymous Coward

                検索したら他でも貼りまくってるから意図的だろ

              • by Anonymous Coward

                以前紹介したときのリンクをコピペしたのでミスです。すみません。
                sradは消せないので厄介ですね。
                ただ、ACで書き込んでいる時は特定されたくはありません。間違って埋め込まれた時に変に指摘しないで欲しいです。
                こっちじゃなくてAmazon側にでも通報すれば向こう側で適切に対処するでしょう。

              • by Anonymous Coward

                同じ間違いを他のサイトでも繰り返さないように,コピペ用のリンクを今すぐに書き換えておくといいかも.
                ところで通報ってやったことないからわからないんですが,あなたが間違いですって報告するのは駄目なんですか?

              • by Anonymous Coward

                他には一件しかないはずです。そちらのコピペです。
                ここ以外に二件以上あるなら第三者によるものです。閲覧数的にまずないと思います。
                意図的でない点は説明した通りですし、今までアフィリエイト収入が発生したことはありません。
                必要ならAmazon側にメールなどで問い合わせていただいても構いません。

              • by Anonymous Coward

                コピペ元のリンクは別サイトの物でAmazonアソシエイトの利用規約に則ったもの…だと思います。性質上書き換えられません。
                こんな事書いたなと思ってざっと漁っただけです。
                sradにはダイレクトメッセージのような機能はないので不特定多数に知らせずに私に依頼する事はできません。

              • by Anonymous Coward

                ま、次回以降は「https://www.amazon.co.jp/exec/obidos/ASIN/453578728X/」って感じで
                後半をカットして載せるこったな

        • by Anonymous Coward

          指数が十分に小さければそうだけど、太陽系の寿命で収まるようなオーダーになるとは思えない

      • by Anonymous Coward

        その認識はNSAや各国の諜報機関に役割や立場について誤解している。
        彼らは保守的で現状の破滅的な変化を望まない。
        制限付きで暗号の安全性が担保されている現状が一番都合が良い。
        自分たちが暗号を自由にできるということは自分らも安全に暗号を使うことができないということ。
        つまり誰も得をしない。

    • by Anonymous Coward

      たとえP=NPでも、どうせものすごく次数の高い多項式オーダーだったりするでしょうから、実用上は大して関係ないです。
      どんなNP完全問題も2次オーダーで済むというなら話は別ですが……

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

    数学ガールでいつの日にか扱われ、ミルカさん大暴れ(大活躍の意)となる日を待ってみよう。

  • by Anonymous Coward on 2017年08月16日 23時26分 (#3262284)

    要旨を読むと、先行研究で列挙されている日本人研究者がいますね。

    先行研究はmonotone network complexityの場合で、この論文はnon-monotone network complexity
    なのか、なるほど分からん。

    • by fromage (48081) on 2017年08月17日 22時31分 (#3262868) 日記

      この論文に関する次の情報から読み解けた範囲で、monotone network complexity、non-monotone network complexity の意味を含む、先行研究の流れを説明します(以下に書いてあることを鵜呑みにしているので、個別の結果は理解していません)。

      間違いを見つけた方はコメントで教えていただけると助かります。

      monotone network complexity は単調回路(AND 素子と OR 素子だけで構成される回路)の複雑さ、 non-monotone network complexity は非単調回路(AND 素子と OR 素子に加えて、NOT 素子も含む回路)の複雑さをそれぞれ示しています [Hacker, IEICE]。[IEICE] では、AND 素子、OR 素子、NOT 素子を含む回路のことを非単調回路ではなく、論理回路と呼んでいます。

      単調回路の図による例(大きさ3 のクリークがグラフに含まれるかの判定)が Wikipedia の図 [wikipedia.org]にあります。ただし、一番下の頂点はクリークを構成するために選択された辺を示しています。また、非単調回路の例が [IEICE] の2ページ目に図 6.1 論理回路として示されています。

      これまでに、(命題1) 「クリーク判定問題を解く単調回路の大きさは、入力の大きさ n の指数倍必要になる」ことがわかっています [Hacker]。また、(命題2) 「非単調回路を使って、ある判定問題を解こうとするとき、入力の長さ n の多項式倍の大きさの非単調回路で解けないならば、その判定問題を解く多項式時間アルゴリズムは存在しない」ことも示されています [Trevisan]。

      (命題1) では単調回路が対象ですが、非単調回路の場合はその大きさが同じ(NOT 素子を使わなければ良い)か小さくなるかのどちらかです。非単調回路でも、n の指数倍の大きさになるなら、(命題2) からクリーク判定問題は多項式時間で解くアルゴリズムのない、P に含まれない問題だと導けます。逆に、非単調回路では n の多項式倍の大きさまで小さくなるなら、(命題2) を適用できないため、P と NP の関係を示すために、非単調関数に対する (命題1) の結果は使えず、P vs. NP は未解決のままです。

      この論文では、(命題1) における単調回路を非単調回路に拡張した場合でも指数倍の大きさの回路が必要であることを示すことによって、(命題2) の結果から、クリーク判定問題は P に含まれない問題であり、P != NP であることを結論づけている [Trevisan]、という感じです。

      親コメント
    • by Anonymous Coward

      「重大な予想を解いたとされる日本人」といえば、望月氏のABC論文から5年たちますね。

typodupeerror

「科学者は100%安全だと保証できないものは動かしてはならない」、科学者「えっ」、プログラマ「えっ」

読み込み中...