证明:SAT属于NP 3-CNF-SAT ·只需要证明把一个实例代入公式进行布 Formula in conjunctive normal form 尔运算即可,其复杂度是多项式没有任 何问题! f(clause)A(clause, )A.A(clause) ·【有优先级的公式计算问题是多项式 Where clauses contains only - v and 的】 variables(variables and - -variables called SAT是NP-hard的:我们可以把 Circuit literals Satisfiable问题约简为SAT问题,而后证 3-conjunctive-normal-form: every clause 明约简过程是多项式的和充要的 contains exactly 3 liter 清华大学宋域恒 请华大学宋恒 3- CNF-SAT是NP完全的 The Clique Problem 验证是多项式的,没有问题 Clique Problem (Hi): A clique is a complete subgraph of G. Here above G is a graph CLIQUE=(<G, k> G is a graph with a Theorem: Clique problem is NP-complete 清华大学末斌恒 请华大学宋恒 Vertex-Co Hamiltonian-cycle A vertex-cover of an undirected graph G=(V, E)is A Hamiltonian cycle is a sequence of v a subset V contains in V such that if (u, v)in E such that it runs all the vertices once exactly then u in V or v in V(or both). excepting the start and end vertex is the A vertex-cover problem is to find a vertex cover same one(it runs two times), and the of m size in a given graph running sequence is a path of the graph ecision problem: VERTEX-COVER=(<G, k: G as a vertex cover of size k) HAM-CYCLE is belong to npc · VERTEX-COVER属于NPC 清华大学末破恒 请华大学宋9 清华大学 宋斌恒 49 证明：SAT属于NP • 只需要证明把一个实例代入公式进行布 尔运算即可，其复杂度是多项式没有任 何问题！ • 【有优先级的公式计算问题是多项式 的】 • SAT是NP－hard的：我们可以把Circuit－ Satisfiable问题约简为SAT问题，而后证 明约简过程是多项式的和充要的 清华大学 宋斌恒 50 3－CNF－SAT • Formula in conjunctive normal form: ¬∧∨→↔ • f= (clause1) ∧ (clause2) ∧ …∧ (clausek) – Where clauses contains only ¬, ∨ and variables(variables and ¬variables called literials) • 3-conjunctive-normal-form: every clause contains exactly 3 literals. 清华大学 宋斌恒 51 3-CNF-SAT是NP完全的 • 验证是多项式的，没有问题 清华大学 宋斌恒 52 The Clique Problem • Clique Problem（团）：A clique is a complete subgraph of G. Here above G is a graph. • CLIQUE={<G,k>:G is a graph with a clique of size k} • Theorem: Clique problem is NP-complete 清华大学 宋斌恒 53 Vertex-Cover problem • A vertex-cover of an undirected graph G=(V,E) is a subset V’ contains in V such that if (u,v) in E, then u in V’ or v in V’(or both). • A vertex-cover problem is to find a vertex cover of minimum size in a given graph • Decision problem: VERTEX-COVER={<G,k>:G has a vertex cover of size k} • VERTEX-COVER 属于 NPC 清华大学 宋斌恒 54 Hamiltonian-cycle • A Hamiltonian cycle is a sequence of V such that it runs all the vertices once exactly excepting the start and end vertex is the same one(it runs two times), and the running sequence is a path of the graph. • HAM-CYCLE is belong to NPC