首页 > 其他 > 详细

P、NP、NPC、NPH问题介绍

时间:2020-06-27 18:23:01      阅读:101      评论:0      收藏:0      [点我收藏+]
  • 几者的关系:

    • 技术分享图片
  • P类问题

    • 在多项式时间内可以解决的问题

  • NP问题

    • 针对一个答案在多项式时间内判断正确性的问题。因为验证一个答案的时间一定不大于解决问题的时间,所以P类问题是NP问题的子集

  • 要搞明白NPC和NPH问题,要先明白规约的概念

  • 规约

    • 通俗地讲,问题A能够用问题B的方法解决,那么A可以规约成B(A是B的一种类型)。类似于求解一元一次方程和求解一元二次方程的关系,前者可以规约成后者。可以看出,后者比前者的难度更大、复杂度更高、使用范围更广。

  • NPC问题:

    • NPC问题满足两个条件:首先,是NP问题;其次,任意NP问题可以在多项式时间内规约为这个问题。

    • 提出NPC问题是为了将所有的NP问题总结(规约)成一个NPC问题,只要解决这个NPC问题,就可以得到解决所有NP问题的通用做法,比如可以将NP问题看做求解一元一次方程,NPC问题看做求解一元二次方程,前者可以看做后者的一个特殊类型,而只要解决了后者,前者就可以解决(套一元二次解的公式)。

    • NPC问题是NP问题的标准形式,一般NP问题是NPC问题的特殊类型。因为规约的原因,NPC问题是NP问题中最难的,想要找到多项式时间内的算法十分困难。

    • 如果找到多项式时间内的NPC问题的算法,那么就可以证明NP=P。

  • NPH问题

    • 满足NPC问题的第二个条件(即任意NP问题可以在多项式时间内规约成该问题)。

    • NPC问题是NP问题和NPH问题的交集。NPH问题的难度不低于NPC问题。

  • 参考资料

 

  

P、NP、NPC、NPH问题介绍

原文:https://www.cnblogs.com/lylhome/p/13198854.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!