算法导论课件第18讲NPCompleteness1章节

1、1,NP-Completeness proof,Three classes of problems P: problems solvable in poly time. NP: problems verifiable in poly time. NPC: problems in NP and as hard as any problem in NP.,2,NP-Completeness (verifiable),For example, suppose that for a given instance G, u, v, k of the decision problem PATH, we are also given a path p from u to v. We can easily check whether the length of p is at most k, and if so, we can view p as a “certificate“ that the instance indeed belongs to PATH.,3,NP-Completeness (v

2、erifiable),例如，假定对判定问题 PATH的一个给定实例 G, u, v, k 同时也给定了一条从u到v的路径 p 。 我们可以检查p的长度是否至多为k 。如果是的，就可以把p看做是该实例的确属于PATH的 “证书”。,4,NP-Completeness (verifiable),Verifiable in poly time: given a certificate of a solution, could verify the certificate is correct in poly time. Examples: Hamiltonian-cycle, given a certificate of a sequence (v1,v2, vn), easily verified in poly time.,5,NP-Completeness (verifiable),The problem of finding a hamiltonian cycle in an undirected graph has been studied for over a hundred y

3、ears. Formally, a hamiltonian cycle of an undirected graph G = (V, E) is a simple cycle that contains each vertex in V . A graph that contains a hamiltonian cycle is said to be hamiltonian; otherwise, it is nonhamiltonian.,(a) A graph representing the vertices, edges, and faces of a dodecahedron, with a hamiltonian cycle shown by shaded edges. (b) A bipartite graph with an odd number of vertices. Any such graph is nonhamiltonian.,6,NP-Completeness (verifiable),We can define the hamiltonian-cycle

4、 problem, “Does a graph G have a hamiltonian cycle?“ as a formal language: HAM-CYCLE = G : G is a hamiltonian graph.,7,NP-Completeness (verifiable),Consider a slightly easier problem. Suppose that a friend tells you that a given graph G is hamiltonian, and then offers to prove it by giving you the vertices in order along the hamiltonian cycle. It would certainly be easy enough to verify the proof: simply verify that the provided cycle is hamiltonian by checking whether it is a permutation of the

5、 vertices of V and whether each of the consecutive edges along the cycle actually exists in the graph. This verification algorithm can certainly be implemented to run in O(n2) time, where n is the length of the encoding of G. Thus, a proof that a hamiltonian cycle exists in a graph can be verified in polynomial time.,8,NP-Completeness (verifiable),We define a verification algorithm as being a two-argument algorithm A, where one argument is an ordinary input string x and the other is a binary str

6、ing y called a certificate. A two-argument algorithm A verifies an input string x if there exists a certificate y such that A(x, y) = 1. The language verified by a verification algorithm A is L = x 0, 1* : there exists y 0, 1* such that A(x, y) = 1.,9,NP-Completeness (verifiable),Intuitively, an algorithm A verifies a language L if for any string x L, there is a certificate y that A can use to prove that x L. Moreover, for any string x L, there must be no certificate proving that x L. For exampl

7、e, in the hamiltonian-cycle problem, the certificate is the list of vertices in the hamiltonian cycle. If a graph is hamiltonian, the hamiltonian cycle itself offers enough information to verify this fact. Conversely, if a graph is not hamiltonian, there is no list of vertices that can fool the verification algorithm into believing that the graph is hamiltonian, since the verification algorithm carefully checks the proposed “cycle“ to be sure.,10,Relation among P, NP, NPC,P NP (Sure) NPC NP (sur

8、e) P = NP (or P NP, or P NP) ? NPC = NP (or NPC NP, or NPC NP) ? P NP: one of the deepest, most perplexing open research problems in (theoretical) computer science since 1971.,11,Arguments about P, NP, NPC,No poly algorithm found for any NPC problem (even so many NPC problems) No proof that a poly algorithm cannot exist for any of NPC problems, (even having tried so long so hard). Most theoretical computer scientists believe that NPC is intractable (i.e., hard, and P NP).,12,View of Theoretical

9、Computer Scientists on P, NP, NPC,NPC,P,NP,P NP, NPC NP, P NPC = ,13,First NP-complete problemCircuit Satisfiability (problem definition),Boolean combinational circuit Boolean combinational elements, wired together Each element, inputs and outputs (binary) Limit the number of outputs to 1. Called logic gates: NOT gate, AND gate, OR gate. true table: giving the outputs for each setting of inputs true assignment: a set of boolean inputs. satisfying assignment: a true assignment causing the output to be 1. A circuit is satisfiable if it has a satisfying assignment.,14,Boolean combinational circuits are built from boolean combinational elements that are interconnected by wires. A boolean combinational element is any circuit element that has a constant number of boolean inputs and outputs and that performs a well-defined function. Boolean values are drawn from the set 0, 1, where 0 represents FALSE and 1 represents TRUE.,15,The boo

《算法导论课件第18讲NPCompleteness1章节》由会员E****分享，可在线阅读，更多相关《算法导论课件第18讲NPCompleteness1章节》请在金锄头文库上搜索。