首页 > 代码库 > 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问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。