常复杂的，事实上当时的学术界一直怀疑是否真的有这种问题存在。
    但牛人终究是牛人，在提出了这类问题后，斯蒂芬·库克还真找到了一个问题，并通过图灵机的方式，证明了他提出的这个问题就属于NPC问题，也就是NP完全问题。
    其定义为“给出一个含有
    个逻辑变量的逻辑表达式，判断这个表达式是否可能取值为真，也就是判断这个逻辑表达式是否是可被满足的。”因为这个定义，所以该类问题又被称作为“可满足性问题”。
    这里不需要管斯蒂芬·库克开了多大的脑洞，反正他通过这种方式证明了他提出的问题属于NPC问题之后，数学界著名的库克定理就此诞生“可满足性问题是一个NPC”问题。
    当斯蒂芬·库克完成了这个开创性的工作之后，次年得到启发的数学家便一连找出了21个NPC类问题。比如大名鼎鼎的“哈密顿循环”、“背包问题”、“三位匹配问题”等等。
    当然最重要的并不是这些问题被发现，而是根据学术界对NPC问题的定义二：任何其它NP类问题都可以归约到这个问题，那么只需要找到任意一个NPC问题中多项式时间复杂度的算法，也意味着能够证明NP=P。
    然而
 <本章未完请点击"下一页"继续观看!>