丈夫志四海,万里犹比邻。这篇文章主要讲述P VS NP相关的知识,希望能为你提供帮助。
目录
-
1.1 P
- 1.1.1 NP
- 1.1.2 Certifiers and certificates: satisfiability
-
2.1 Certifiers and certificates: Hamilton path
- 2.1.1 Some problems in NP
-
3.1 P, NP, and EXP
- 3.1.1 The main question: P vs. NP
1.1 PDef. Algorithm A runs in polynomial time if for every string s, A(s)
terminates in ≤ p( ?s?) “steps,” where p(?) is some polynomial function.
1.1.1 NP
Def. Algorithm C(s, t) is a certifier for problem X if for every string s : s ∈ X iff there exists a string t such that C(s, t) = yes.
NP = set of decision problems for which there exists a poly-time certifier.
?C(s, t) is a poly-time algorithm.
?Certificate t is of polynomial size: ?t? ≤ p(?s?) for some polynomial p(?)
关于NP举一个例子:
文章图片
- 我们找是否有两个数相乘等于437669
- 首先我们找到了一个可验证的解就是541
- 那么只要我们可以找多项式时间内找到809我们就可以找到原问题的解。
- 3-SAT. SAT where each clause contains exactly 3 literals.
- Certificate. An assignment of truth values to the Boolean variables.
- Certifier. Check that each clause in Φ has at least one true literal.
- 首先我们找到其中一个解作为验证实例比如x1=true,x2=tru2,x3=false,x4=false;
- 我们必须在多项式时间内可以验证这个解是成立的!
simple path P that visits every node?
Certificate: A permutation π of the n nodes.
Certifier: Check that π contains each node in V exactly once,
and that G contains an edge between each pair of adjacent nodes
2.1.1 Some problems in NP
文章图片
3.1 P, NP, and EXPP. Decision problems for which there exists a poly-time algorithm.
NP. Decision problems for which there exists a poly-time certifier.
EXP. Decision problems for which there exists an exponential-time algorithm.
3.1.1 The main question: P vs. NP
Does P = NP? [Cook 1971, Edmonds, Levin, Yablonski, G?del]
Is the decision problem as easy as the certification problem?
文章图片
If yes… Efficient algorithms for 3-SAT, TSP, VERTEX-COVER, FACTOR, …
If no… No efficient algorithms possible for 3-SAT, TSP, VERTEX-COVER, …
推荐阅读
- 滤镜也能复制粘贴(视频编辑服务专属滤镜一键搞定)
- Linux之tar命令
- Kubernetes Cronjob的第一次使用
- 9DNS主从和iptables使用
- JVM升级篇八(工具篇)
- 更便捷的Mybatis插件——EasyMybatis
- Linux 脚本初步等练习
- oeasy教您玩转vim - 84 - #命令command
- 设计模式-- 外观模式(没那么高大上)