100万ドルの懸賞問題P ≠ NP予想

クレイ数学研究所によって１００万ドルの懸賞金がかけられている７つのミレニアム懸賞問題の中の、６つの未解決問題の１つ。解決した問題はポアンカレ予想である。一般にアルゴリズムの有無を問うのが決定問題であったが、アルゴリズムがあるときに、その計算効率を研究するのが計算の複雑さの理論である。例えば、命題論理式が与えられ、その 原子命題【原子命題】論理結合子を含まない命題を原子命題と呼ぶ。 に真か偽かの値を代入して全体を真にできるかどうかを問う問題は決定可能であり、SAT【SAT】SATisfiability Problem（充足可能性問題）の頭文字。命題の要素となる変数(原子命題)に真偽を割り当てて命題全体を真にできるかという問題。 と呼ばれる。SATに対しては、何らかの(非決定的な)方法で適当な代入例が得られれば、それによって全体が真になるかどうかは論理式の長さに対して多項式時間で確認できるので、SATはNPに属する。対して、非決定的な動作が認められず、地道に計算を遂行し、入力の長さに対して多項式時間で正しく答えられるような問題はPに属するという。SATはNPの中でも最も難しい問題の１つで、もしこれがPに属することが言えれば、NPとPは一致する。しかし、両者は同じでないとする見方が優勢である。