复杂性和难解性

证明一个问题的难解性与寻找有效算法一样难.

但是NP完全性理论提供了许多简单的方法, 来证明一个给定问题与大量其他问题"一样的难", 而这些问题普遍被认为是很困难的.

知道一个问题是NP完全的, 给我们提供了有价值的信息, 一定不要优先寻找有效的, 精确的算法, 比较适当的途径是集中精力找其他达到次一级目标的算法.
例如, 可以寻找解决这个问题的各种特殊情况的有效算法 ,或者寻找在大多数情况下都能快速运算的算法, 或者放松问题的某个方面.

问题 通常含有若干个参数, 这些参数的值还没有指定.
问题的描述通过给定:
1 所有参数的一般性描述
2 陈述解需要满足的性质
给问题的所有参数指定了具体的参数, 就得到了问题的一个实例

有许多不同的方式能够描述问题的实例, 假定已经选定了一种具体的方式, 即与一种固定的编码方案相联系, 这个编码方案吧问题的实例映射到描述字符串. PROBLEM的INSTANCE的输入长度定义为由PROBLEM的编码方案得到的INSTANCE的描述的符号数.

一个算法是O(f(n))的是说,这个算法的绝对值以f(n)的绝对值的某个正常数倍为上界.

耗时对比

大多数指数时间算法只是穷举搜索的变种,而多项式时间的算法通常只有对问题的结构有了某些比较深入的了解之后才有可能给出. 很多人都认为, 只有知道了问题的多项式时间算法才能认为"很好地解决了"这个问题.

有些指数时间算法在实际中十分有用. 作为定义, 时间复杂性是一种worst-case最坏情况的度量, 时间复杂性为2^n的算法仅仅表示至少有一个规模为n的问题实例需要这么多时间, 而大多数问题实例可能实际上需要远比这个少得多的时间.

• 已经证明线性规划的单纯形算法具有指数时间复杂度, 但在实际中计算得很好.
• 背包问题的分支界限法也具有指数时间复杂度, 但也算的很好.
  但一般只有少数几个被认为在实际中是很有用的.

产生难解性的两种原因

• 问题本身太难了, 需要指数时间才能找到解.
• 解本身太大了, 以致于不可能用长度不超过poly(input size)的表达式来描述

发现问题之间的相互联系, 常常可以给算法设计人员提供有用的信息.
证明两个问题相关的基本方法是通过给出一个构造性变换, 把第一个问题的实例map到第二个问题的实例, 从而把第一个问题reduce成第二个问题.

Stephen Cook 1971 paper "The Complexity of Theorem Proving Procedures"(定理证明过程的复杂性)一文奠定了NP完全性理论的基础.