当前位置 博文首页 > 文章内容

    NP-complete

    作者: 栏目:未分类 时间:2020-11-14 15:01:13

    本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
    说我们IIS7站长博客,有一篇博文用了他们的图片。
    要求我们给他们一张图片6000元。要不然法院告我们

    为避免不必要的麻烦,IIS7站长博客,全站内容图片下架、并积极应诉
    博文内容全部不再显示,请需要相关资讯的站长朋友到必应搜索。谢谢!

    另祝:版权碰瓷诈骗团伙,早日弃暗投明。

    相关新闻:借版权之名、行诈骗之实,周某因犯诈骗罪被判处有期徒刑十一年六个月

    叹!百花齐放的时代,渐行渐远!



    1.1 NP-complete

    NP-complete: A problem Y ∈ NP with the property that for every problem X ∈ NP, X ≤ P Y

    NPC问题指的是一个问题首先它是一个NP问题其次所有的NP问题都可以规约到这个问题。

    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

    逻辑电路问题是世界上第一个NPC问题,它是这样描述的,首先给你一个逻辑电路图一定可以在多项式时间内验证一个解,但是也有可能你永远无法找到一个满足的解(其实通过简单的与或非门构造一个解始终为FALSE的电路是很简单的)。那么这样它就是一个NP问题,我们再思考第二个条件:所有的计算问题到最后进行计算机运算的时候都是通过与或非门运算的因此所有的NP问题都可以规约到逻辑电路问题。因此逻辑电路问题是一个NPC问题。

    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.

    如果y是一个NP问题,我们选择一个NPC问题,如果x可以规约到y,那么y也是一个NPC问题。

    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.

    证明上面的推论:我们任选一个NP问题W,w可规约到x,x可规约到y.根据传递性w可规约到y.
    因此Y是一个NPC问题。

    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

    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 NP

    Asymmetry of NP: We need short certificates only for yes instances.

    np对称性是指一个NP的反面也是NP问题比如下面的两个对等问题。

    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