P≠NP予想証明への歴史 - 発明・発見年表

数学、あるいは計算機科学の未解決問題であるP≠NP予想の歴史。

予想の年表

1950まで　チューリングマシン

1965 ハートマニス、スターンズ、計算複雑さの論文、時間内に解けるかどうかの枠組を議論

指数関数的時間がかかる問題が発見されはじめる。

1965 コッバム、エドモンズ、論文のなかでクラスPを定義。これで予想の片方が定義された。

1971 カナダのクック、予想の発見。NPの問題群が定義される。NPの問題に高速なアルゴリズムがあれば、ほかのすべての問題に対して高速なアルゴリズムが存在する、と発見した。

そんなアルゴリズムはない、というのがこの予想であり、事実この予想は正しい、と考えられている。

1972 カープがさまざまな分野の問題がNP完全であることを証明。ハミルトン路問題などがふくまれる。

1973 ソ連のレビン、NP完全性を独立に発見していた。

1980後半　あるサーキットに関して解決をみたが、その後停滞。

1991 戸田の定理の発見

現状、まだ未解決である。予想は正しいと考えられている。

都合のいいアルゴリズムは無さそうなので、なるべく速めに解けるアルゴリズムを開発していくのも同時に行われている。

ミシェルスキー「P≠NP予想は現代数学最大の問題」

スメール「予想は現代数学でもっとも美しい未解決問題」

ラズボロフ「なぜこんなに難しいかというと、多くの素晴らしい数学者が夢中になってかんがえて、何一つできなかったからだ」

フォートナウの「ゴールデンチケット」という本のなかで、SF小説のようにこの場合が示される。

高速でとくアルゴリズムの発見

高速アルゴリズムの発見自体を問題にして、もとの高速アルゴリズムでとけばよい。

これにより更に高速化

問題がつぎつぎ高速で解かれるようにぬり、社会問題も解決！