コンピューターの計算理論における未解決問題の一つ。多項式時間以内で解けるアルゴリズムが存在するクラスPの問題と、多項式時間以内で効率よく解けるアルゴリズムは見つかっていないが、ある解があらかじめ与えられたとき、それが正しいかどうかを多項式時間以内で判定できるクラスNPの問題を考えるとき、クラスNPに属し、かつクラスPに属さない問題が存在するかどうか明らかではないというもの。すなわち、現実的な範囲の時間内で計算可能なクラスPと解の検証は可能であるクラスNPは同じではないという予想を意味する。ミレニアム問題の一つとしても知られる。P≠NP予想。P対NP予想。
