NP问题
Howard Yin 2020-12-25 16:00:02 数学算法
- NP表示“Non-Deterministic Polynomial”——“非确定的多项式”
- 解可以在多项式时间内验证
- 非确定的图灵机在多项式时间内可以解决
- P表示“Polynomial”——“多项式”
- 是一个NP问题
- 确定的图灵机在多项式时间内可以解决
- “NPC”表示“Non-Deterministic Polynomial Complete”——“非确定的多项式完全”
- 是一个NP问题
- 任何NP问题都可以在多项式时间内规约到这个问题
- “NPH”表示“Non-Deterministic Polynomial Hard”——“非确定的多项式难”
- 解不能在多项式时间内验证
- 任何NP问题都可以在多项式时间内规约到这个问题
P问题和NP问题的解都可以在多项式时间内验证
# 3CNF-SAT问题
给定n个布尔变量x1,x2,x3…xn和一个布尔表达式C,形式为:
- 由一系列子句合取组成:C=C1∧C2∧C3∧⋯∧CM
- 每个子句由三个变量析取而成:Cm=(xi∨xj∨xk)
求使布尔表达式为真的布尔变量x1,x2,x3…xn值。
显然,对于一组布尔变量x1,x2,x3…xn值,依次求解每个子句的值,再求其析取的值即得最终的值,时间复杂度为O(n),是NP问题。
# K团问题
“k团”是指一种有k个点的子图,子图中的点两两之间都有边相连。
k团问题就是给定一个图G和整数k,求G的k团。
显然,对于G中的任意k个顶点组合,只需要判断两两之间是否有边即可判断是否是k团,时间复杂度O(n2),是NP问题。
# 汉密尔顿回路问题
汉密尔顿回路是指一条经过无向图中所有点且每个点只经过一次的路径。
汉密尔顿回路问题就是给定一个图G寻找它的汉密尔顿回路。
显然,对于n个顶点的排列,只需要依次判断顶点之间是否重复以及相邻顶点间是否有边即可验证是否是汉密尔顿回路,时间复杂度为O(n),是NP问题。
# 深入理解:最优化问题和判定问题
一个最优化问题可以和一个判定问题对应起来:
- 判定问题验证一个解是否满足条件
- 最优化问题找出所有满足条件的解,或从满足条件的解中找出最好的解
P、NP、NPC可以如下表示:
- P类最优化问题:
- 对应的判定问题可以在多项式时间内解决
- 对应的最优化问题可以在多项式时间内解决
- NP类最优化问题:
- 对应的判定问题可以在多项式时间内解决
- 对应的最优化问题不一定能在多项式时间内解决
- NPC类最优化问题:
- 对应的判定问题可以在多项式时间内解决
- 对应的最优化问题不一定能在多项式时间内解决
- 所有的NP问题都可以在多项式时间内归约到这个问题
- NPH类最优化问题:
- 对应的判定问题不能在多项式时间内解决
- 所有的NP问题都可以在多项式时间内归约到这个问题
# NPC的意义
- 若能证明某个NP完全问题多项式时间可解,则所有NP问题均可多项式时间求解,从而有P=NP。
- 若能证明某个NP完全问题多项式时间不可解,则所有NP问题均不可多项式时间求解,从而有P=NP。
目前是否有P=NP还在探索之中,普遍认为P=NP。
# 如何证明一个问题是NPC问题
- 证明该问题是一个NP问题:找出一个多项式时间内验证解的办法
- 将该问题规约到一个NPC问题:找出一个多项式时间内将某个已知NPC问题的解转化为该问题的解的办法,并证明当且仅当NPC问题有解时该问题有解
# 基本的NP完全问题
- SAT问题(Boolean Satisfiability Problem)
- 最大团问题(Maximum Clique Problem)
- 图着色问题(Graph Coloring Problem)
- 哈密顿回路问题(Hamiltonian Cycle Problem)
- TSP问题(Traveling Salesman Problem)
- 顶点覆盖问题(Vertex Cover Problem)
- 最长路径问题(Longest Path Problem)
- 子集和问题(Sum of Subset Problem)