- 151 名前：１３２人目の素数さん [02/08/14 06:22]
- >148
マイケル・ラビンなど，この分野の天才たちが挑戦してきた
歴史的に有名な問題です．もっとも，ＮＰ∩co-NPに含まれることは
自明なので，NP-hardではなかろうと信じられてきました．
ラビンらのアルゴリズムはこれをさらに小さなRPというクラスに
押し下げるものでしたが，リーマン予想云々という条件が
出てきた時点でこれ以上の結果はそう簡単にはでないだろうと
思ってましたので，このニュースには本当にびっくりしました．
いまだにNP-hardnessが未解決な問題として残されているのは
グラフに関する問題が多いです．一番有名なのはグラフ同型問題です．
これなどは，Pに含まれることは絶対にないだろうと思われています．
なぜかというと，もしそれが真ならば，Ｐ＝ＮＰはおろか
無限の多項式階層が有限個につぶれてしまうからです．
ＮＰというクラスはこの階層のもっとも下に位置します．
かれらの論文はまだ未発表ですが，それはおそらく
次のACM STOCに投稿するつもりだからではないでしょうか．
チューリング賞を授与するこの世界で最も権威のある会議ですから．
〆切は12月ぐらいだったと思います．
こんなニュースを聞くと，未解決問題に挑戦したくなりますが
私にはリスクが大きすぎます．人生は有限なので（ｗ
|
 |
