1. Polynomial-Time Solvability
-- A problem is polynomial-time solvable if there is an algorithm that correctly solves it in O(n^k ) time, for some constant k.
-- P = the set of poly-time solvable problems.
a) Cycle-free shortest paths in graphs with negative cycles is NP-Complete
b) Knapsack [running time of our algorithm was (nW), but input length proportional to logW] is NP-complete
2. Traveling Salesman Problem
-- Input: Complete undirected graph with nonnegative edge costs.
-- Output: A min-cost tour [i.e., a cycle that visits every vertex exactly once].
3. Reductions
-- Definition: Problem P1 reduces to problem P2 if: given a polynomial-time subroutine for P2, can use it to solve P1 in polynomial time.
-- Computing the median reduces to sorting
-- Detecting a cycle reduces to depth-first search
-- All pairs shortest paths reduces to single-source shortest paths
4. Completeness
-- Suppose P1 reduces to P2, if P1 is not in P, then neither is P2. ==> P2 is at least as hard as P1.
-- Let C = a set of problems. The problem P is C-complete if:
(1) P in C
(2) everything in C reduces to P.
That is: P is the hardest problem in all of C.
5. Choice of the Class C
-- Halting Problem: Given a program and an input for it, will it eventually halt?
-- Fact: No algorithm, however slow, solves the Halting Problem.
-- TSP definitely solvable in finite time (via brute-force search). TSP is as hard as all brute-force-solvable problems.
6. The Class NP
-- A problem is in NP if:
(1) Solutions always have length polynomial in the input size
(2) Purported solutions can be verified in polynomial time.
-- Examples:
(1) Is there a TSP tour with length <= 1000?
(2) Constraint satisfaction problems. (3-SAT)
7. Interpretation of NP-Completeness
-- Every problem in NP can be solved by brute-force search in exponential time. [Just check every candidate solution.]
-- Fact: Vast majority of natural computational problems are in NP [Can recognize a solution]
-- A polynomial-time algorithm for one NP-complete problem solves every problem in NP efficiently [implies that P=NP]
-- NP-completeness is strong evidence of intractability.
8. Proving that a problem P is NP-complete
-- Find a known NP-complete problem P' (see Garey and Johnson, "Computers and Intractability")
-- Prove that P' reduces to P
-- implies that P at least as hard as P'
-- P is NP-complete as well (assuming P is an NP problem)
9. The P vs. NP Question
-- NP : "Nondeterministic Polynomial"
-- Widely conjectured: P<>NP
-- (psychological) if P=NP, someone would have proved it by now
-- (philosophical) if P=NP, then finding a proof always as easy as verifying one
-- (mathematical) not known, insane richness of the space of polynomial time algorithms
10. Three Useful Strategies to Approach NP-Complete Problems
-- Focus on computationally tractable special cases
-- WIS in path graphs, trees and bounded tree widths graph.(NP-C in general graphs)
-- Knapsack with polynomial size capacity (e.g., W = O(n))
-- 2SAT (P) instead of 3SAT (NP-C)
-- Vertex cover when optimal solution is small. (a smart kind of exaustive search)
-- Heuristics - fast algorithms that are not always correct
-- Greedy and dynamic programming-based heuristics for knapsack.
-- Solve in exponential time but faster than brute-force search.
-- Knapsack (O(n) instead of O(2^n))
-- TSP (approximately 2^n instead of n!)
-- Vertex cover (n 2^OPT instead of n^OPT)
相关推荐
Garey M R & Johnson D S - Computer And Intractability - A Guide To The Theory Of NP-Completeness
COMPUTERS AND INTRACTABILITY: A Guide to the Theory of NP-Completeness by Michael R. Garey & David S. Johnson Content 1 Computers, Complexity, and Intractability 1 1.1 Introduction 1 1.2 ...
名家经典,单栏阅读,pdf格式,非常清晰,
known to be NP-complete, and the collection of such problems continues to grow almost daily. Indeed, the NP-complete problems are now so pervasive that it is important for anyone concerned with the ...
The Theory of NP-Completeness
NP 完全问题的经典之作 好不容易找到的
Data Structures and Algorithms (Vol 2. Graph Algorithms and NP-Completeness) Data Structures and Algorithms (Vol 2. Graph Algorithms and NP-Completeness)
关于NP理论的经典书籍,几乎所有NP理论的论文都会引用的参考书。
David Johnson 发表于ACM Transaction on Algorithm上的关于NPC进展的专栏,作者AT&T的著名计算机科学家。
计算复杂性理论经典教材,Garey&Johnson
有效应对NP完整性对于2020年秋季产品,我们的任务是解决NP完全问题的近似方法。 您可以在以及project_sec.pdf查看项目规范。 我们选择将此问题表示为要求Python 3.6+ 或 请注意,如果您使用的是Gurobi,则需要获得...
to the Theory of NP-Completeness, M. R. Garey and D. S. Johnson, Editor: W.H. Freeman and Compagny, 1979. • Introduction to the theory of computa- tion. Michael Sipser, PWS Publishing Compagny, 1997....
Chapter 34 - NP-Completeness Chapter 35 - Approximation Algorithms Part VIII - Appendix: Mathematical Background Appendix A - Summations Appendix B - Sets, Etc. Appendix C - Counting and ...
Chapter 34 - NP-Completeness Chapter 35 - Approximation Algorithms Part VIII - Appendix: Mathematical Background Appendix A - Summations Appendix B - Sets, Etc. Appendix C - Counting and ...
Chapter 34 - NP-Completeness Chapter 35 - Approximation Algorithms Part VIII - Appendix: Mathematical Background Appendix A - Summations Appendix B - Sets, Etc. Appendix C - Counting and ...
Theory of Computational Complexity offers a thorough presentation of the fundamentals of complexity theory, including NP-completeness theory, the polynomial-time hierarchy, relativization, and the ...
Chapter 34 - NP-Completeness Chapter 35 - Approximation Algorithms Part VIII - Appendix: Mathematical Background Appendix A - Summations Appendix B - Sets, Etc. Appendix C - Counting and ...
Chapter 34 - NP-Completeness Chapter 35 - Approximation Algorithms Part VIII - Appendix: Mathematical Background Appendix A - Summations Appendix B - Sets, Etc. Appendix C - Counting and ...