P/NP问题是什么?
来源:学生作业帮 编辑:搜搜做题作业网作业帮 分类:综合作业 时间:2024/08/15 18:37:02
P/NP问题是什么?
![P/NP问题是什么?](/uploads/image/z/16137108-36-8.jpg?t=P%2FNP%E9%97%AE%E9%A2%98%E6%98%AF%E4%BB%80%E4%B9%88%3F)
P/NP问题是在理论信息学中计算复杂度理论领域里至今没有解决的问题,它被“克雷数学研究所”(Clay Mathematics Institute,简称CMI)在千禧年大奖难题中收录.P/NP问题中包含了复杂度类P与NP的关系.1971年史提芬·古克(Stephen A.Cook) 和 Leonid Levin 相对独立的提出了下面的问题,即是否两个复杂度类P和NP是恒等的(P=NP?)
再问: 好快
再问: 好快