复旦大学：《数据结构与算法设计 Data Structures and Algorithm》课程英文讲义_Chapter 12 NP-complete problems

Data Structures and Algorithm Xiaoqing Zheng Zhengxq@fudan.edu.cn

Data Structures and Algorithm Data Structures and Algorithm Xiaoqing Zheng zhengxq@fudan.edu.cn

Polynomial time algorithms Almost all the algorithms we have studied thus far have been polynomial-time algorithms On input of size n, their worst-case running time is O(nk) for some constant k

Pol l lh ynomia l time a lgorit hms Al ll h l i h h di d h f Almost all t he a lgor i t hms we have studi e d t hus far have been polynomial-time algorithms. y Oi fi n input o f s ize n, th i e ir worst-case runniii ng t ime i s O ( n k ) for some constant k

Undecidable HALTS(P, X DIAGONAL(X 1. a: if HALTS(X, X) then goto a else halt How about DIAGONAL(DIAGONAL)

Und d bl ecidable HALTS(P, X) DIAGO AN L(X) 1. a: if HALTS(X, X) 2. then goto a 3. else halt How about DIAGONAL(DIAGONAL)

Shortest vs longest simple paths Shortest simple path Given a directed graph G=(V, E), find the shortest simple path between two vertices Longest simple path Given a directed graph G=(v, E), find the longest simple path between two vertices

Sh l l h Shortest vs. longest simp le pat h s Sh i l h Shortest s imp le pat h Given a directed graph G = ( V, E ) , find the shortest si l hb i imp le pat h between two vert ices. Longest simple path Longest simple path Given a directed graph G = ( V, E ) , find the longest simple path between two vertices simple path between two vertices

Konigsberg's Bridges problem D B The river Pregel divides the town of Konigsberg into four separate land masses, A, B, C, and D Seven bridges connect the various parts of town, C and some of the town's curious citizens wondered if it were possible to take a journey across all seven bridges without having to cross B any bridge more than once

Konigsb ' d bl berg's Bri dges Problem A C D B The river Pregel divides the town of Konigsberg The river Pregel divides the town of Konigsberg A into four separate land masses, A, B, C, and D. Seven bridges connect the various parts of town, C D Seven bridges connect the various parts of town, and some of the town's curious citizens wondered if it were possible to take a journey B across all seven bridges without having to cross any bridge more than once

Euler tour vs. Hamiltonian cycle Euler tour An Euler tour of a connected, directed graph G=(, E) s a cycle that traverses each edge of g exactly once Hamiltonian cycle An Hamiltonian cycle of a directed graph G=(V, E)is a simple cycle that contains each vertex in v

Eul ll er tour vs. Hami ltonian cyc l e E l u ler tour An Euler tour of a connected, directed graph G = ( V, E ) i lh s a cyc le t hat traverses each d e dge o f G exact ly once. Hamiltonian cycle Hamiltonian cycle An Hamiltonian cycle of a directed graph G = ( V, E ) is a simple cycle that contains a simple cycle that contains each vertex each vertex in V

Euler tour

Euler tour b a b c a c d d e f g

Traveling salesman problem

T l l bl Trave ling sa lesman problem

Analysis of traveling salesman problem Given a finite number of cities" along with the cost of travel between each pair of them, find the cheapest way of visiting each city exactly once and finishing at the city he starts from ·19 Cities Possible routes=18=6.40237x1015 life time=80×365×24×60×60 3.1536×10 Computer speed=10000 routes/second 253.77 Generation!

Analysis of traveling salesman problem Gi fi i b f " i i " l i h h Given a fi n ite num ber o f " c i t ies " a long w i t h t he cost of travel between each pair of them, find the cheapest way of i i i h i l d fi i hi f v i s i t ing eac h c ity exact ly once an d fi n i shing at the city he starts from. y 19 Cities y Possible routes = 18! = 6.40237 × 1015 y life time = 80 × 365 × 24 × 60 × 60 = 3,1536 × 10 9 y Computer speed = 10000 routes /second 253.77 Generation!

Certificate The class NP consists of those problems that are verifiable" in polynomial time If we were given a certificate of a solution, then we could verify that the "certificate"is correct in time polynomial in the size of the input to the problem P C NP P CnP or P= np The Clay Mathematics Institute is offering a USSI million reward to anyone who has a formal proof that problem

C f erti icate y Th l e c ass NP consi f h bl h ists of those problems that are "verifiable" in polynomial time. y If i we were given a certificate of li h a solution, then we could verify that the "certificate" is correct in time pol i l i h i f h i h bl lynomial in the size of the input to the problem. P NP ⊆ P NP ⊂ or P = NP Th Cl M h I ff US$1 ll d The Clay Mathematics Institute is offering a US$1 million reward to anyone who has a formal proof that problem