p対NP問題、完全多項式対非決定性多項式問題、計算複雑性（理論計算機科学と数学のサブフィールド）において、いわゆるNP問題はすべて実際にP問題であるかどうかの問題である。 P問題は、”多項式時間”で解くことができる問題であり、アルゴリズムのステップ数がnの多項式関数で制限されるようなアルゴリズムが存在することを意味します。nは問題の入力の長さに対応します。, したがって、P問題は容易である、または扱いやすいと言われています。 問題は、その解が多項式時間で推測および検証できる場合にNPと呼ばれ、非決定的とは、推測を行うための特定の規則に従わないことを意味します。

線形計画問題はNPであり、1947年にアメリカの数学者George Dantzigによって発明されたsimplex法のステップ数は入力のサイズとともに指数関数的に増加する。 しかし、1979年にロシアの数学者Leonid Khachianは多項式時間アルゴリズムを発見しました。, 計算ステップの数は、指数関数的ではなく、変数の数のべき乗として増加し、それによって線形計画問題が実際にPであることを示します。p問題はNP問題のサブセットであるため、その解のアルゴリズムをNP問題またはp問題を解決するために修正できる場合、問題はNP困難です。 （しかし、すべてのNP困難な問題がNP問題のクラスのメンバーであるわけではありません。）NPとNP困難の両方である問題は、NP完全であると言われています。, したがって、任意のNP完全問題に対する効率的なアルゴリズムを見つけることは、このクラスに属する任意の問題に対する解がクラスの他のメンバー, 1971年、アメリカの計算機科学者スティーブン-クックは、充足可能性問題（ブール代数の式の変数に値を代入して、その文が真であるようにする問題）がNP完全であることを証明し、これがNP完全であることが示された最初の問題であり、NP完全問題のクラスのメンバーである他の問題を示す方法を開いた。 ＮＰ完全問題の有名な例は，輸送スケジュールの最適化に広く応用されている旅行セールスマン問題である。, NP完全問題に対して多項式時間アルゴリズムが見つかるかどうかは分かっておらず、これらの問題が扱いやすいか扱いにくいかを判断することは理論計算機科学における最も重要な問題の一つである。 このような発見は、P=NP=NP完全であることを証明し、コンピュータ科学と数学の多くの分野に革命をもたらすでしょう。

たとえば、現代の暗号は、二つの大きな素数の積を因数分解することはPではないという仮定に依存しています。, 二つの素数の積を検証するのは簡単です（多項式時間）が、二つの素因数を計算するのは難しいことに注意してください。 発見の効率的なアルゴリズムのための素因数も最も近代的な暗号化する仕組みである。

2000年にアメリカの数学者スティーブン-スメールは、18の21世紀に解決するための重要な数学的問題の影響力のあるリストを考案しました。 彼のリストの第三の問題は、P対NP問題でした。, また、2000年には、アメリカ合衆国マサチューセッツ州ケンブリッジのクレイ数学研究所によって特別賞に選ばれた七つの数学的問題の一つであるミレニアム問題に指定され それぞれのミレニアム問題の解決策は$1百万の価値があります。