＼閲覧ありがとうございます！当サイトではリンク広告を利用しています／
数学、あるいは計算機科学の未解決問題であるP≠NP予想の歴史。
1950まで チューリングマシン
1965 ハートマニス、スターンズ、計算複雑さの論文、時間内に解けるかどうかの枠組を議論
指数関数的時間がかかる問題が発見されはじめる。
1965 コッバム、エドモンズ、論文のなかでクラスPを定義。これで予想の片方が定義された。
1971 カナダのクック、予想の発見。NPの問題群が定義される。NPの問題に高速なアルゴリズムがあれば、ほかのすべての問題に対して高速なアルゴリズムが存在する、と発見した。
そんなアルゴリズムはない、というのがこの予想であり、事実この予想は正しい、と考えられている。
1972 カープがさまざまな分野の問題がNP完全であることを証明。ハミルトン路問題などがふくまれる。
1973 ソ連のレビン、NP完全性を独立に発見していた。
1980後半 あるサーキットに関して解決をみたが、その後停滞。
1991 戸田の定理の発見
現状、まだ未解決である。予想は正しいと考えられている。
都合のいいアルゴリズムは無さそうなので、なるべく速めに解けるアルゴリズムを開発していくのも同時に行われている。
ミシェルスキー「P≠NP予想は現代数学最大の問題」
スメール「予想は現代数学でもっとも美しい未解決問題」
ラズボロフ「なぜこんなに難しいかというと、多くの素晴らしい数学者が夢中になってかんがえて、何一つできなかったからだ」
フォートナウの「ゴールデンチケット」という本のなかで、SF小説のようにこの場合が示される。
高速でとくアルゴリズムの発見
高速アルゴリズムの発見自体を問題にして、もとの高速アルゴリズムでとけばよい。
これにより更に高速化
問題がつぎつぎ高速で解かれるようにぬり、社会問題も解決！