第1个回答 2017-02-14
世界七大数学难题之一：P/NP问题
P/NP问题是在理论信息学中计算复杂度理论领域里至今没有解决的问题，它也是克雷数学研究所七个千禧年大奖难题之一。P/NP问题中包含了复杂度类P与NP的关系。1971年史提芬·古克（Stephen A. Cook）和Leonid Levin相对独立的提出了下面的问题，即是否两个复杂度类P和NP是恒等的（P=NP?）。
复杂度类P即为所有可以由一个确定型图灵机在多项式表达的时间内解决的问题；类NP由所有可以在多项式时间内验证解是否正确的决定问题组成，或者等效的说，那些解可以在非确定型图灵机上在多项式时间内找出的问题的集合。很可能，计算理论最大的未解决问题就是关于这两类的关系的：本回答被提问者采纳