現時点では、複雑さPとNPのクラスが互いに等しいか等しくないことは証明されていません。ただし、多項式アルゴリズムで解決できるかどうかは不明なNPタスクがいくつかあります。これらのタスクはnp-fullと呼ばれます。1つのNP完全タスクを多項式アルゴリズムによって解決できることが証明された場合、すべてのNPの問題は多項式アルゴリズムによって解決することもでき、PとNPは等しくなります。

それにもかかわらず、この仮説を確認または反論することができる証拠はまだ発見されていません。現在、複雑さPとNPのクラスの平等の問題（オーバーブロウの問題としても知られるロシア語を話すソース）は、アルゴリズムの理論における未解決の問題のままです。彼女はミレニアムの7つのタスクの1つであり、粘土数学研究所が100万米ドルに賞を任命した解決策のためです。
На данный момент не доказано, что классы сложности P и NP равны или не равны друг другу. Однако существует несколько задач NP, для которых неизвестно, могут ли они быть решены полиномиальным алгоритмом. Эти задачи называются NP-полными. Если бы было доказано, что одна NP-полная задача может быть решена полиномиальным алгоритмом, то все NP-проблемы также могли бы быть решены полиномиальными алгоритмами, и P и NP были бы равны.

Тем не менее, до сих пор не найдено никаких доказательств, которые могли бы подтвердить или опровергнуть эту гипотезу. В настоящее время вопрос о равенстве классов сложности P и NP (в русскоязычных источниках также известный как проблема перебора) остаётся открытой проблемой в теории алгоритмов. Она является одной из семи задач тысячелетия, за решение которой Математический институт Клэя назначил премию в миллион долларов США.