P vs NP問題とは、計算量理論において、PクラスとNPクラスが同値であるか否かを問う問題です。
まず、Pクラスとは、多項式時間で解ける問題の集合を表します。つまり、ある問題がPクラスに属しているとは、その問題を解くために必要な計算量が、入力のサイズに対して多項式時間で済むということを意味します。一方、NPクラスとは、多項式時間で検証可能な問題の集合を表します。つまり、ある問題がNPクラスに属しているとは、その問題の解が与えられた場合に、その解が正しいかどうかを多項式時間で検証できるということを意味します。
従って、Pクラスに属する問題は効率的に解ける問題であり、NPクラスに属する問題は正解を効率的に検証できる問題であると言えます。
P vs NP問題は、つまり、PクラスとNPクラスが同値であるか否かを問う問題です。もし、PクラスとNPクラスが同値であるならば、NPクラスに属する問題も多項式時間で解くことができるため、多くの現実的な問題が効率的に解けるようになるでしょう。一方、もしPクラスとNPクラスが同値でない場合、NPクラスに属する問題は効率的に解けない問題であり、現実的な問題の多くが解けないことになります。
現在までにP vs NP問題の解決策は見つかっていません。この問題は、計算理論の基本問題として、多くの研究者によって取り組まれています。しかし、この問題が解決された場合でも、それが実際の現実世界にどのような影響をもたらすかは分かっていません。