計算機科学の未解決問題
Pとは多項式時間で解答の見つかる問題のクラスを表し、これに対しNPは多項式時間で解答が検証できる問題のクラスを表す。クラスPの問題は同時にクラスNPであることは証明されている(つまりP⊆NP)。
ここでP≠NP問題とは、NPがPに含まれるのかどうか(P⊃NPかどうか)、すなわちPとNPは等しいのか(P=NPかどうか)という問題のことである。この問題の解決は、計算機がもつある種の限界を証明することにあたるため、広く注目されている。
もしPとNPが同じクラスであれば(つまりP=NPであれば)、素因数分解や充足可能性問題など現在効率的な算法の存在しない問題を解くことができる。P≠NP予想という名前も示すとおり、現在PとNPは異なるクラスであろうと予想されているが、証明されていない。