2017-06-02 P≠NP予想が嫌い P≠NP予想 - Wikipedia 多くの研究者が長年にわたって多項式時間オーダーのアルゴリズムの開発に取り組んでいるにもかかわらず、そのような効率的なアルゴリズムは見つかっていない。このことがP≠NP予想の根拠の一つとなっている。 別にP=NPでもP≠NPでもどっちでもよいし、世の中的にはP≠NPの方が安全なのは知ってるけど、傲慢な感じがして嫌。まあ、たぶんP=NPだけどね。 追記 今の自分の感触でいくと、最大クリーク問題だとグラフが大きくなればなるほど多項式に近くなるイメージがある。なのでNP=ZPPっていわれる方がしっくりくる。平均的には多項式で終わるが、最悪はもっとかかる(指数時間)がイメージには近い。