首页 > 代码库 > NPC问题

NPC问题

  研一是密码学专业开的一门课《计算复杂性理论》,当时对立面的NP,NPC这些概念都挺模糊,后来也是不了了之。现在看一些密码学论文的时候经常遇到这一概念,只能硬着头皮搞清楚。下面把自己的理解写下来,一来加深记忆和理解,而来为以后做个储备。

  问题分为两种,一种是可以通过明确的公式直接得到答案,比如:1+1=?

                         另一种无法直接通过公式求解,比如:给一个数,求出它的因子。

  对于第二种问题我们求解的途径只能通过猜测验证,例如,我们一个数N的因子的时候,一般方法是猜测因子为a,取a=2,然后验证N是否能被a整除,是,则2是因子,否,则a加1继续验证,直到a取到N-1,找出所有的因子。

  第二种问题就称为非确定性问题。在非确定性问题中,验证一个猜测的步骤在多项式时间内可完成,则称为多项式非确定性问题,即NP问题。在NP问题中,验证每一个猜测所用的时间是指数时间。在NP问题中,存在特定的NP问题,其他所有的NP问题都能在多项式时间内转化为该问题,这个NP问题称为NP完全问题,即NPC。所以如果存在一种算法,能在多项式时间内求出NPC问题的正确答案,那么就能在多项式时间内求出所有的NP问题。目前这种算法还没出现。这就是NP是否等于P的问题(能在多项式时间求解的问题称为P问题)。

NPC问题