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 ...
《计算机与难解性:NP完全性理论指南》是一本由Michael R. Garey和David S. Johnson共同编写的经典著作,深入探讨了计算复杂性理论中的NP完全性问题。该书是理解NP完全性概念及其在算法设计、优化问题解决以及计算...
《NP完全理论》 在计算机科学领域,NP完全理论是算法复杂性理论的一个核心部分,主要研究的是在有限计算时间内解决复杂问题的能力。这个理论主要关注两类问题:P类问题和NP类问题。 P类问题是指那些可以用确定性的...
### 数据结构与算法(第二卷:图算法与NP完全性) #### 标题解析 《数据结构与算法(第二卷:图算法与NP完全性)》这一标题清晰地表明了本书的主题聚焦于两个核心概念:“图算法”和“NP完全性”。其中,“图算法...
David Johnson 发表于ACM Transaction on Algorithm上的关于NPC进展的专栏,作者AT&T的著名计算机科学家。
该问题涉及到了NP完全性,这是计算复杂性理论中的一个重要概念,它表明问题的解法很难找到且可能需要指数级的时间。NP完全问题通常被视为在实际计算中无法有效解决的难题。 在活动时间调度问题中,我们有n个任务,...
计算复杂性理论经典教材,Garey&Johnson
### NP-Completeness概念解析与理解 #### 一、引言 在计算机科学领域,算法设计与分析是解决计算问题的核心。本章介绍了一个极为重要的概念——NP-完全(NP-Completeness)。这一概念不仅对理论计算机科学至关重要...
有效应对NP完整性对于2020年秋季产品,我们的任务是解决NP完全问题的近似方法。 您可以在以及project_sec.pdf查看项目规范。 我们选择将此问题表示为要求Python 3.6+ 或 请注意,如果您使用的是Gurobi,则需要获得...
NP-completeness是指一个问题是否可以在多项式时间复杂度内解决。NP-complete问题是指无法在多项式时间复杂度内解决的问题。 3. 解决NP-hard问题的方法 解决NP-hard问题可以通过以下方法: * Sacrifice 解决问题...
这些策略可以help us cope with NP-completeness,解决NP-hard问题。 详细地,以下是相关知识点: * 不可追溯性(Intractability):指无法在多项式时间内解决某些问题的现象。 * NP-hard问题:指无法在多项式时间...
例如,可以通过将图的k-coloring问题归约为3-coloring问题,或把4-D匹配问题归约为3-D匹配问题,来证明这些问题的NP-completeness。 总结来说,NP完全性证明是研究计算复杂性的重要工具,它帮助我们理解哪些问题是...
Computers And Intractability A Guide To The Theory Of
本章“Chapter 8 The THEORY OF NP_COMPLETENESS”主要探讨了NP类、P类、NP难问题以及NP完全问题的概念。 首先,NP(非确定性多项式时间)类是决策问题的集合,这些问题可以通过非确定性多项式算法来解决。这意味着...
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 ...