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

それにもかかわらず、この仮説を確認または反論することができる証拠はまだ発見されていません。現在、複雑さPとNPのクラスの平等の問題（オーバーブロウの問題としても知られるロシア語を話すソース）は、アルゴリズムの理論における未解決の問題のままです。彼女はミレニアムの7つのタスクの1つであり、粘土数学研究所が100万米ドルに賞を任命した解決策のためです。