P≠NP予想
ミレニアム懸賞問題
「計算複雑性理論におけるクラスPとクラスNPが等しくない」という予想
クラスP
コンピュータを使って、多項式時間で解ける問題の集合 クラスNP
コンピュータを使って、多項式時間で答えの正誤が確認できる問題の集合
「クラスPではないがクラスNPであることはわかる」という実例は山ほどあるが、「クラスNPに所属している問題がクラスPではない」ことの証明は極めて困難。
「正誤の確認」はたいていの場合、値を当てはめるだけになっているが、「すべての可能性」の中から正しい答えの一つを探すことは総当たりでは無限の時間がかかってしまう。何らかのアルゴリズムによりその中の1つを選び出す必要があるが、そのアルゴリズムが多項式時間でできるかというと