NP完全问题

图灵机的定义

• 确定性图灵机的定义
  一台图灵机M是一个七元组，{Q，Σ，□，Γ，δ，q0,qaccept}，其中 Q，Σ，Γ 都是有限集合，且满足：

（1）Q 是有限状态集合；

（2）Σ是输入字母表，其中不包含特殊的空白符 □；

（3）Γ 是带子上字母表，其中 □∈Γ且Σ∈Γ ；

（4）δ：Q×Γ→Q×Γ×{L,R}是转移函数，其中L,R 表示读写头是向左移还是向右移；

（5）q0∈Q是起始状态；

（6）qaccept是接受状态；

（7）□ 是空白字符（唯一允许在任何一步出现无数次的字符）

• 非确定性图灵机的定义
  Μ=(Q，Σ，β，□，Α，δ）, where

（1）Q 是有限状态集合

（2）Σ 是符号表

（3）β∈Q 是起始状态

（4）□∈Σ 是空白字符

（5）Α⊆Q 是接受状态

（6）δ( Q\Α×Σ)×(Q×Σ×{L,R,S}) 是状态转移函数（\表示不包括）

NP，P，NP完全问题，NP困难问题的定义

• P问题是可以用确定图灵机在多项式时间（Polynomial time）解决的问题

• NP问题是可以用非确定性图灵机（Non-deterministic Turing Machine）在多项式时间内解决的问题。

  从充分条件上来说，对于问题L，只要满足下面的条件，就是NP完全问题

  1. L是NP问题(任何一个答案，都能迅速验证是否是正确的，但是没有有效的解决方案).

  2. NP中的任何问题都可以在多项式时间内被简化成该问题（简化方法另外叙述）

• NP困难问题，就是只需要满足上述第2个条件的问题

三个问题的关系如下

关系图

相关讨论

好了上面是相关的定义和基础，我们来看看为什么要讨论这些东西，为什么会有这些定义

对于使用算法解决复杂的问题，比如最短路径，欧拉图，MST等等，我们已经设计了成功的算法，所以我们会问：

“能够用计算机解决所有可计算的问题吗？”，“有没有可计算的问题即使用无限时间都无法用算法解决？”，图灵停机问题（给出程序和代码，返回是否会无限运行）给出了一个答案，图灵停机问题是一个NP困难问题，图灵利用计算机和程序的数学化定义，证明了停机问题不可能存在一个通用的算法

不过对于解决NP完全问题，许多尝试都是失败的，NP完全问题是状态未知的问题，目前为止没有发现任何能够解决该问题的多项式时间算法，也没有任何证明这样的算法不存在。不过有趣的是，如果任何一个NP完全问题被证明可以在多项式时间内解决，那么所有这些问题都可以被解决

当然NP问题也可以通过一种凭运气的算法在多项式时间内解决，只要算法能保证每次的选择都是正确的

简化方法（Reduction）

假设L1和L2是两个问题，A2是L2的解决方案，也就是说，对于任何符合L2的要求的输入，A2都能给出答案。那么我们只要找到L1到L2的转化方法，那么A2自然就变成L1的解决方案了

Reduction

比如说如果要计算加权有向图的最小权积（就是求用边的乘积表示路径时的最小路径），我们只需要利用类似Dijkstra的求最小路径算法，记录下每个路径的权值，最后求得结果，而不必重新创造一种算法

NP完全问题

为什么我们要了解NP完全问题

了解NP完全问题对我们是很有帮助的，比如说你要写一个算法。去给你的公司解决一个非常非常重要的问题。那么你想了半天，想出一个指数时间的算法，结果发现一直超时根本算不出来，只能跟领导报告说抱歉我的锅。但是如果你了解NP完全问题，你可以尝试去证明这个是NP完全问题，一旦证明出来了，就可以马上给公司报告说这个问题目前不可能存在多项式时间内的解决方案，因为这属于一个很著名的未解决问题“P=NP？”。

如何证明L是NP完全的：

根据定义的话，必须证明所有NP问题都可以在多项式的时间内被简化到L，显然这几乎不可能。不过我们还有其他路子，也就是把已知的NP完全问题简化到L。只要找出多项式时间内的简化方法，那么我们就能证明该问题是NP完全问题

如何证明第一个NP完全问题：

显然上面的定义是一个递归定义，自然而然也引出了先有鸡还是先有蛋的问题。SAT (Boolean satisfiability problem) 是第一个被Cook证明的NP完全问题。

https://www.geeksforgeeks.org/np-completeness-set-1/