アカウント名:
パスワード:
P=NP のほうが色々と役立つし
もう20年来、否定の予想で専門家の間では定着しているから、今さら肯定的結論では、そちらの方が大混乱だよ。セキュリティ関連への悪影響と最適化問題への有用性だと、今はもう悪影響の方が大きいんじゃないかな。
(肯定的に)証明できても、解が直ちにわかるわけじゃないから、どうってことない気もするが。
自分の名前をパスワードにしても直ちに破られる訳ではないからどうってことないと言っているほどに、おめでたい。
P=NPは決定問題なので、直ぐに何かが起こるという結論の間には実は、ギャップがある。
P=NPである、というのは、おなじみの巡回セールスマン問題で言うと、「全長x未満の経路はある?」にYes/Noの解を求めるアルゴリズムが存在する、と言う意味。直ぐに分かることとして、2分探索をすれば、「最短の経路長は?」という問題も解ける。
ただ、「最短の経路を求めよ」という問題はまた別。
「もしも」の話をするなら、「P=NP」が証明された上で、「最短の経路を求めよ」の方は多項式オーダーでは解けないと証明される、という超展開もあり得る。
「P!=NP」→「最適化問題問題の方も解けない」、とか、「最適化問題が解けた」→「P=NP」とかは真なので、「どうせP!=NPなんだからそこまで深く考えなくても」とスルーされがちだけど。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
アレゲは一日にしてならず -- アレゲ見習い
間違いであってほしい (スコア:0)
P=NP のほうが色々と役立つし
Re: (スコア:1)
もう20年来、否定の予想で専門家の間では定着しているから、
今さら肯定的結論では、そちらの方が大混乱だよ。
セキュリティ関連への悪影響と最適化問題への有用性だと、今はもう
悪影響の方が大きいんじゃないかな。
Re: (スコア:0)
(肯定的に)証明できても、解が直ちにわかるわけじゃないから、どうってことない気もするが。
Re: (スコア:0)
自分の名前をパスワードにしても直ちに破られる訳ではないから
どうってことないと言っているほどに、おめでたい。
Re:間違いであってほしい (スコア:0)
P=NPは決定問題なので、直ぐに何かが起こるという結論の間には実は、ギャップがある。
P=NPである、というのは、おなじみの巡回セールスマン問題で言うと、「全長x未満の経路はある?」にYes/Noの解を求めるアルゴリズムが存在する、と言う意味。直ぐに分かることとして、2分探索をすれば、「最短の経路長は?」という問題も解ける。
ただ、「最短の経路を求めよ」という問題はまた別。
「もしも」の話をするなら、「P=NP」が証明された上で、「最短の経路を求めよ」の方は多項式オーダーでは解けないと証明される、という超展開もあり得る。
「P!=NP」→「最適化問題問題の方も解けない」、とか、「最適化問題が解けた」→「P=NP」とかは真なので、「どうせP!=NPなんだからそこまで深く考えなくても」とスルーされがちだけど。