QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 5118|回复: 2
打印 上一主题 下一主题

[其他资源] P,NP,NP-complete,NP-hard的含义

[复制链接]
字体大小: 正常 放大
madio        

3万

主题

1313

听众

5万

积分

  • TA的每日心情
    奋斗
    2024-7-1 22:21
  • 签到天数: 2014 天

    [LV.Master]伴坛终老

    自我介绍
    数学中国站长

    社区QQ达人 邮箱绑定达人 优秀斑竹奖 发帖功臣 风雨历程奖 新人进步奖 最具活力勋章

    群组: 数学建模培训课堂1

    群组: 数学中国美赛辅助报名

    群组: Matlab讨论组

    群组: 2013认证赛A题讨论群组

    群组: 2013认证赛C题讨论群组

    跳转到指定楼层
    1#
    发表于 2013-2-20 07:16 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta |邮箱已经成功绑定
    NP问题就是指其解的正确性可以在多项式时间内被检查的一类问题。比如说数组求和,得到一个解,这个解对不对呢,显然是可以在多项式时间内验证的。再比如说SAT,如果得到一个解,也是能在多项式时间内验证正确性的。所以SAT和求和等等都是NP问题。然后呢,有一部分NP问题的解已经可以在多项式时间内找到,比如数组求和,这部分问题就是NP中比较简单的一部分,被命名为P类问题。那么P以外的NP问题,就是目前还不能够在多项式时间内求解的问题了。会不会将来某一天,有大牛发明了牛算法,把这些问题都在多项式时间内解决呢?也就是说,会不会所有的NP问题,其实都是P类问题呢,只是人类尚未发现呢?NP=P吗?" G& N% t6 j* h- u/ Z* |1 n" H
    6 R9 @  w- q) _8 N7 K0 c
    可想而知,证明NP=P的路途是艰难的,因为NP问题实在太多了,要一一找到多项式算法。这时Stephen A. Cook这位大牛出现了,写了一篇The Complexity of Theorem Proving Procedures,提出了一个NP-complete的概念。NPC指的是NP问题中最难的一部分问题,所有的NP问题都能在多项式时间内归约到NPC上。所谓归约是指,若A归约到B,B很容易解决,则A很容易解决。显然,如果有任何一道NPC问题在多项式时间内解决了,那么所有的NP问题就都成了P类问题,NP=P就得到证明了,这极大的简化了证明过程。那么怎样证明一个问题C是NP完全问题呢?首先,要证明C是NP问题,也就是C的解的正确性容易验证;然后要证明有一个NP完全问题B,能够在多项式时间内归约到C。这就要求必须先存在至少一个NPC问题。这时Cook大牛就在1971年证明了NP完全问题的祖先就是SAT。SAT问题是指给定一个包含n个布尔变量的逻辑式,问是否存在一个取值组合,使得该式被满足。Cook证明了SAT是一个NPC问题,如果SAT容易解决,那么所有NP都容易解决。Cook是怎样做到的呢?
    ( B, _6 e7 g; h! X
    : j, T0 {6 l" {2 Q% C他通过非确定性图灵机做到的。非确定性图灵机是一类特殊的图灵机,这种机器很会猜,只要问题有一个解,它就能够在多项式时间内猜到。Cook证明了,SAT总结了该机器在计算过程中必须满足的所有约束条件,任何一个NP问题在这种机器上的计算过程,都可以描述成一个SAT问题。所以,如果你能有一个解决SAT的好算法,你就能够解决非确定性图灵机的计算问题,因为NP问题在非图机上都是多项式解决的,所以你解决了SAT,就能解决所有NP,因此——SAT是一个NP完全问题。感谢Cook,我们已经有了一个NPC问题,剩下的就好办了,用归约来证明就可以了。目前人们已经发现了成千上万的NPC问题,解决一个,NP=P就得证,可以得千年大奖(我认为还能立刻获得图灵奖)。
    5 M: r- ^. Z- e0 Z* P8 W
    1 ]! T4 E, g% x  K. l9 C6 J那么肯定有人要问了,那么NP之外,还有一些连验证解都不能多项式解决的问题呢。这部分问题,就算是NP=P,都不一定能多项式解决,被命名为NP-hard问题。NP-hard太难了,怎样找到一个完美的女朋友就是NP-hard问题。一个NP-hard问题,可以被一个NP完全问题归约到,也就是说,如果有一个NP-hard得到解决,那么所有NP也就都得到解决了。
    9 p2 W+ m" b- D$ V0 a; }- u $ Z& M5 [4 q7 s: a. T  P5 ?; c. _
    NP-Hard和NP-Complete 区别8 w0 Z: q3 u& f" ~' F

    * K8 I8 K2 d' \0 `4 t对NP-Hard问题和NP-Complete问题的一个直观的理解就是指那些很难(很可能是不可能)找到多项式时间算法的问题. 因此一般初学算法的人都会问这样一个问题: NP-Hard和NP-Complete有什么不同? 简单的回答是根据定义, 如果所有NP问题都可以多项式归约到问题A, 那么问题A就是NP-Hard; 如果问题A既是NP-Hard又是NP, 那么它就是NP-Complete. 从定义我们很容易看出, NP-Hard问题类包含了NP-Complete类. 但进一步的我们会问, 是否有属于NP-Hard但不属于NP-Complete的问题呢? 答案是肯定的. 例如停机问题, 也即给出一个程序和输入, 判定它的运行是否会终止. 停机问题是不可判的, 那它当然也不是NP问题. 但对于SAT这样的NP-Complete问题, 却可以多项式归约到停机问题. 因为我们可以构造程序A, 该程序对输入的公式穷举其变量的所有赋值, 如果存在赋值使其为真, 则停机, 否则进入无限循环. 这样, 判断公式是否可满足便转化为判断以公式为输入的程序A是否停机. 所以, 停机问题是NP-Hard而不是NP-Complete.
    ( H* h0 i5 c* }' | + U5 Z  G& z. E
    让我冒着出错被人砸版砖的危险来解释一下P/NP/NP-Complete/NP-Hard。
    " y8 _- [9 ?% m; Q! `  
    . B- P. ?/ H# s) \  1,计算复杂性 % m! }  J& R" z# y! V5 d/ N$ E1 P
      这是描述一种算法需要多少“时间”的度量。(也有空间复杂性,但因为它们能相互转换,所以通常我们就说时间复杂性。对于大小为 n 的输入,我们用含 n 的简化式子来表达。(所谓简化式子,就是忽略系数、常数,仅保留最“大”的那部分)
    6 o; C/ l+ y" l' e' T6 S) O   比如找出 n 个数中最大的一个,很简单,就是把第一个数和第二个比,其中大的那个再和第三个比,依次类推,总共要比 n-1 次,我们记作 O(n) (对于 n 可以是很大很大的情况下,-1可以忽略不计了)。
    + i" V; g0 I+ [  t6 i' l   再比如从小到大排好的 n 个数,从中找出等于 x 的那个。一种方法是按着顺序从头到尾一个个找,最好情况是第一个就是 x,最坏情况是比较了 n 次直最后一个,因此最坏情况下的计算复杂度也是 O(n)。还有一种方法:先取中间那个数和 x 比较,如偏大则在前一半数中找,如偏小则在后一半数中找,每次都是取中间的那个数进行比较,则最坏情况是 lg(n)/lg2。忽略系数lg2,算法复杂度是O(lgn)。8 g4 @5 @7 |# X- x5 [1 V3 u
       ! f: d* V% G% |& g* j' g
      2,计算复杂性的排序: - k, d7 u2 q' \5 Z/ x; |; r
      根据含 n 的表达式随 n 增大的增长速度,可以将它们排序:1 < lg(n) < n < nlg(n) < n^2 < ... < n^k (k是常数)< ... < 2^n。最后这个 2 的 n 次方就是级数增长了,读过棋盘上放麦粒故事的人都知道这个增长速度有多快。而之前的那些都是 n 的多项式时间的复杂度。为什么我们在这里忽略所有的系数、常数,例如 2*n^3+9*n^2 可以被简化为 n^3?用集合什么的都能解释,我忘了精确的说法了。如果你还记得微积分的话就想像一下对 (2*n^3+9*n^2)/(n^3) 求导,结果是0,没区别,对不?
      `- _& S' q) l& s- n   . G# r6 h% Q) O3 U+ S# l
      2,P 问题:对一个问题,凡是能找到计算复杂度可以表示为多项式的确定算法,这个问题就属于 P (polynomial) 问题。
    $ ~( [, q' B, U+ m; Q; s   + a7 `2 @/ H5 q" F0 X
      3,NP 问题: ) r6 n& P2 m: u  a8 |7 B6 c, D
      NP 中的 N 是指非确定的(non-deterministic)算法,这是这样一种算法:(1)猜一个答案。(2)验证这个答案是否正确。(3)只要存在某次验证,答案是正确的,则该算法得解。+ |: R6 c1 T- |$ t6 [
      NP (non-deterministic polynomial)问题就是指,用这样的非确定的算法,验证步骤(2)有多项式时间的计算复杂度的算法。
    & X! [! W4 u" b% ^   # g" t# A0 n/ L- J7 o: z
      4,问题的归约: & G2 \5 w( k& o5 r
      这……我该用什么术语来解释呢?集合?太难说清了……如果你还记得函数的映射的话就比较容易想象了。
    ; y3 q- Y8 |% ?5 C! W# v  大致就是这样:找从问题1的所有输入到问题2的所有输入的对应,如果相应的,也能有问题2的所有输出到问题1的所有输出的对应,则若我们找到了问题2的解法,就能通过输入、输出的对应关系,得到问题1的解法。由此我们说问题1可归约到问题2。5 h# z! z( b6 q4 n  R* l; k
      
    ' r2 h4 q0 k4 t0 g  5,NP-Hard:
    ; k- R. ~! m1 E/ N& g  有这样一种问题,所有 NP 问题都可以归约到这种问题,我们称之为 NP-hard 问题。 ! |3 I$ H4 a8 B
      
    6 M" c0 Q) A* Q5 ?! J+ p  6,NP完全问题 (NP-Complete):
    + P1 y- I' b  E- d  如果一个问题既是 NP 问题又是 NP-Hard 问题,则它是 NP-Complete 问题。可满足性问题就是一个 NP 完全问题,此外著名的给图染色、哈密尔顿环、背包、货郎问题都是 NP 完全问题。
    ! f' l* T, Z! V- T. `  G8 f) M   
    ( r1 v# O2 d! R8 t, }0 x& R6 ~+ Q9 A  从直觉上说,P<=NP<=NP-Complete<=NP-Hard,问题的难度递增。但目前只能证明 P 属于 NP,究竟 P=NP 还是 P 真包含于 NP 还未知。
    " x" \4 O: W! ^/ Y
    zan
    转播转播0 分享淘帖0 分享分享1 收藏收藏0 支持支持0 反对反对0 微信微信
    数学建模社会化

    1

    主题

    9

    听众

    1747

    积分

  • TA的每日心情
    开心
    2016-7-26 21:58
  • 签到天数: 182 天

    [LV.7]常住居民III

    社区QQ达人

    群组: 2014年美赛冲刺培训

    群组: 数学建模培训课堂1

    群组: 物联网工程师培训

    群组: 2014年网络挑战赛交流

    回复

    使用道具 举报

    3#
    无效楼层,该帖已经被删除
    您需要登录后才可以回帖 登录 | 注册地址

    fastpost qq
    收缩
    • 电话咨询

    • 04714969085

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-11-23 07:40 , Processed in 0.564505 second(s), 66 queries .

    回顶部