P与NP问题

VRP卡车调度是NP-hard问题

参考文献地址
数学家有时把“如多项式时间长的算法”视为快速计算,相对应的是超多项式时间,表示任何多项式时间的输入数目只要够大,超多项式时间所需的解题时间终究会大大超过任何多项式时间的问题。指数时间就是一例。

P类问题

所有可以在多项式时间内求解的判定问题构成P类问题。

NP类问题

所有的非确定性多项式时间(例如指数时间)可解的判定问题构成NP类问题。“猜算”的答案正确与否的算法,假如可以在多项式(polynomial)时间内算出来,就叫做多项式非确定性问题。

NPC问题(NP-Complete)

NP中的某些问题的复杂性与整个类的复杂性相关联.这些问题中任何一个如果存在多项式时间的算法,那么所有NP问题都是多项式时间可解的.这些问题被称为NP-完全问题(NPC问题)。(NP=P?的猜想)
不管我们编写程序是否灵巧,判定一个答案是可以很快利用内部知识来验证,还是没有这样的提示而需要花费大量时间来求解,被看作逻辑和计算机科学中最突出的问题之一。它是斯蒂文·考克于1971年陈述的。

举例

生成问题的一个解通常比验证一个给定的解时间花费要多得多。这是这种一般现象的一个例子。与此类似的是,如果某人告诉你,数13,717,421可以写成两个较小的数的乘积,你可能不知道是否应该相信他,但是如果他告诉你他可以因式分解为3607乘上3803,那么你就可以用一个袖珍计算器容易验证这是对的。

请我吃包辣条吧💕