NP完全性精讲

NP-完全问题
● NP-完全问题是这样一个其求解难度未知的
问题类：
■ 至今还没有发现有多项式时间算法来求解
■ 也没有给出其求解时间以超多项式为下界
● 我们把它叫做 P = NP 问题
■ 该问题是计算机科学领域中最大问题。也是一
个21世纪的难题。
NP 是Non-deterministic Polynomial 的缩写
第五章 NP-完全性 NP Completeness
内容提要
•多项式时间,多项式时间归约,多项
式时间可验证算法,多项式时间可判 定算法 •优化问题及其相关的判定问题 •P,NP,NP-难,NP-完全,CO-P,CO-NP •电路可满足性问题是NP-完全问题 •若干NP-完全性问题的证明
重点与难点
l1
l1
l2
l2
强连通分支:
百度文库
l1 l2 l1 l2 l1
结论 2-CNF公式可满足当且仅当其关联有向图中 任一强连通分支上不出现互为否定的文字。
C D与(C x) (x D)有相同的可满足性。
l1 l2 lm1 lm 与 (l1 l2 x1 ) (x1 l3 x2 ) (x2 l4 x3 ) (xm4 lm4 xm3 ) (xm3 lm1 lm ) m3
NP-完全性简介
NP-完全性
● 有的问题是难解的(
intractable):
当问题规模变得越来越大时,我们不能在合 理的时间内求得问题的解. ● 什么才算是合理时间? 标准定义: 多项式时间(polynomial time)
■ 对于规模为 n的输入, 最坏情况时间复杂度为
O(nk) ,其中k是某一常数. ■ 多项式时间: O(n2), O(n3), O(1), O(n lg n) ■ 非多项式时间: O(2n), O(nn), O(n!)
波斯特对应问题实例： Σ=｛0，1｝ 例1. A={1,10,011}, B={101,00,11} 其解为：（1，3，2，3） 1011 10 011 例2. A=｛1，10111，10｝，B=｛111，10，0｝ 其解为(2,1,1,3)或(2,1,1,3,2,1,1,3) 例3.A={10,011,101},B={101,11,011} 这个PCP问题实例无解。
问题
NP-完全性及P类、NP类简介
P类：多项式时间可解的问题类。
NP类：多项式时间可验证的问题类。 P
NP, NPC
NP.
注意：P类问题、NP类问题都是指判定问题
2－CNF可满足问题是P问题。
xy
x y,
y x
例如，F (l1 l2 ) (l1 l2 ) (l1 l2 ) (l1 l2 )
重点: •多项式时间归约 •P,NP,NP-难,NP-完全,CO-P,CO-NP •电路可满足性问题是NP-完全问题 难点:若干NP-完全性问题的证明
学习目的与要求
理解多项式时间 , 多项式时间归约 , 多项式时间可验证算法,多项式时间 可判定算法,优化问题及其相关的判 定 问 题 ,P,NP,NP- 难 ,NP- 完 全 ,COP,CO-NP,电路可满足性问题是NP-完 全问题.掌握若干NP-完全性问题的 证明方法.
多项式时间算法
● 多项式时间可解问题 ■ P表示多项式时间可解的问题类.
● 所有问题都能在多项式时间内可解?
■ 图灵机“停机问题”是不可解问题。不管用多
长时间、多大规模的计算机。 ■ 波斯特(POST)对应问题是不可解问题。 ■ 这些问题是难解问题, 且没有多项式时间算法
POST 对应问题
给定两个有序表A ｛s1,s2 , ,sk｝, B {t1,t2 , ,tk }.A B k.sj,tj 都是二进制代码串。且 |sj | 0, | tj | 0.(j 1,2,,k).问：是否有下 标序列i1, i2 , , in(n 1)使得 si1si2 sin ti1 ti2 tin ?
SHORTEST-PATH要优化的值：路径长度 给定图G，顶点u和v，限界：非负整数 N是自然数集。
kN
最短路径问题SHORTEST-PATH相关联的判 定问题PATH：给定一个图G，顶点u和v及非 负整数k,问是否有u到v的包含边数至多是k的 路径？
优化问题与其相关联的判定问题的难易程度： 如果一个优化问题是容易的，那么其相关联的 判定问题也是容易的。反过来，如果优化问题 的相关联的判定问题是难的，那么优化问题本 身一定是难的是。 SHORTEST-PATH是容易的，因此PATH是容 易的。(为什么?)
归约
设A，B是两个不同的判定问题。
A 是问题A的一个实例，
具有相同的可满足性。
K-CNF:一个布尔公式称为k-CNF公式,如果 它是一个CNF公式且它的每个子句恰有k个 变元或变元的负出现。
可满足公式:一个布尔公式称为可满足的,如 果存在对该公式中的变量的一种赋值，使 得布尔公式取值为真。
k-CNF可满足问题：任给定一个k-CNF公式 F，问F是否可满足？ 2－CNF可满足问题――多项式时间可判定 k-CNF可满足问题――NP-完全（k 3）。
NP－完全理论
概述 问题Q的多项式时间算法：最坏情况时间复 杂度f(n)=O(nk),k是某一常数。
易解问题：有多项式时间算法；
难解问题：需要超多项式时间。
有些问题描述相似但其求解难度有本质不同：
•最短路径问题 V.S. 最长路径问题 •Eular回路问题 V.S. Hamilton回路问题
•2－CNF可满足性问题 V.S. 3-CNF可满足性
判定问题与优化问题
优化问题：有若干个可行解，每个可行解有一个 值与它相关联，求有最优值的可行解。 如最短路径问题SHORTEST-PATH.
判定问题：只要求回答“是”或“不是(YES/NO)
每个优化问题都有其关联的判定问题 （判定问题与优化问题的关系）。 对于一个给定的优化问题，通常对进行优 化的值作限界后可得到关联的判定问题。