P/NP问题

P/NP问题是在理论信息学中计算复杂度理论领域里至今没有解决的问题，它被"克雷数学研究所"(Clay Mathematics Institute, 简称CMI)在千禧年大奖难题中收录。 P/NP问题中包含了复杂度类P与NP的关系。1971年史提芬·古克(Stephen A. Cook) 和 Leonid Levin 相对独立的提出了下面的问题，即是否两个复杂度类P和NP是恒等的(P=NP?)。