嗯，姜先把npc抛出来，结果话锋一转，开始说np。姜到底是说npc还是np呢？不知所云。
cook有一篇经典论文我看过，基本上都是讲npc的。不知道姜说的‘cook曾经证明过’是cook的哪一篇论文证明过
【 在 gnwd 的大作中提到: 】
: 这段话不清晰
:
: 就是所有的NP问题中，有一类问题，被称为NPC问题，Cook曾经证明过，所有的NP问题都可以被规约为合取范式的可满足性问题，这样一来，如果合取范式的可满足性问题有多项式时间的解，那所有的已知的未知的NP问题，都将有多项式时间的解。除了这个合取范式的问题，后来陆陆续续证明了很多问题也是NPC问题，于是，在这么多NPC问题中，只要有一个有突破，所有的NP问题都将有多项式时间算法
: ...................
--
FROM 221.216.143.*