NP-complete _ompl - 锐客网

志不强者智不达，言不信者行不果。这篇文章主要讲述NP-complete相关的知识，希望能为你提供帮助。

目录

1.1 NP-complete
1.1.1 The “first” NP-complete problem
- 1.1.2 Establishing NP-completeness
- 1.1.3 Implications of Karp
- 1.1.4 Implications of Cook–Levin
- 1.1.5 Implications of Karp + Cook–Levin
- 1.1.6 Some NP-complete problems
2.1 Asymmetry of NP
- 2.1.1 NP = co-NP ？

1.1 NP-completeNP-complete: A problem Y ∈ NP with the property that for every problem X ∈ NP, X ≤ P Y
Proposition. Suppose Y ∈ NP-complete. Then, Y ∈ P iff P = NP.
Pf. ? If P = NP, then Y ∈ P because Y ∈ NP.
Pf. ? Suppose Y ∈ P.
?Consider any problem X ∈ NP. Since X ≤ P Y, we have X ∈ P.
?This implies NP ? P.
?We already know P ? NP. Thus P = NP
其实定义一个问题是否是NP问题是很简单的，但是要满足所有的NP问题都可以规约到该问题看起来很难实现，因为NP太多了。。。。
那么是否真正存在我们定义中的NPC问题呢？答案是肯定的！
1.1.1 The “first” NP-complete problem

文章图片

1.1.2 Establishing NP-completeness
Recipe. To prove that Y ∈ NP-complete:
?Step 1. Show that Y ∈ NP.
?Step 2. Choose an NP-complete problem X.
?Step 3. Prove that X ≤ P Y.
Proposition. If X ∈ NP-complete, Y ∈ NP, and X ≤ P Y, then Y ∈ NP-complete.
Pf. Consider any problem W ∈ NP. Then, both W ≤ P X and X ≤ P Y
?By transitivity, W ≤ P Y.
?Hence Y ∈ NP-complete.
1.1.3 Implications of Karp

文章图片

1.1.4 Implications of Cook–Levin
【NP-complete】

文章图片

1.1.5 Implications of Karp + Cook–Levin

文章图片

1.1.6 Some NP-complete problems
Basic genres of NP-complete problems and paradigmatic examples.
?Packing/covering problems: SET-COVER, VERTEX-COVER,INDEPENDENT-SET.
?Constraint satisfaction problems: CIRCUIT-SAT, SAT, 3-SAT.
?Sequencing problems: HAMILTON-CYCLE, TSP.
?Partitioning problems: 3D-MATCHING, 3-COLOR.
?Numerical problems: SUBSET-SUM, KNAPSACK.
2.1 Asymmetry of NPAsymmetry of NP： We need short certificates only for yes instances.

文章图片

2.1.1 NP = co-NP ？
Fundamental open question. Does NP = co-NP?
?Do yes instances have succinct certificates iff no instances do?
?Consensus opinion: no.
关于NP问题是否和CO-np问是完全对等的？
业界公共的意识是：不等的！
Theorem. If NP ≠ co-NP, then P ≠ NP.
Pf idea.
?P is closed under complementation.
?If P = NP, then NP is closed under complementation.
?In other words, NP = co-NP.
?This is the contrapositive of the theorem