Question? Leave a message!




The "first" NP-complete problem

The "first" NP-complete problem
8. INTRACTABILITY II P vs. NP ‣ NPcomplete ‣ coNP ‣ NPhard ‣ Lecture slides by Kevin Wayne
 Copyright © 2005 PearsonAddison Wesley
 http://www.cs.princeton.edu/wayne/kleinbergtardos Last updated on 1/31/17 6:57 AMRecap 3SAT 
 INDEPENDENTSET DIRHAMCYCLE GRAPH3COLOR SUBSETSUM VERTEXCOVER SCHEDULING HAMCYCLE PLANAR3COLOR SETCOVER TSP 3SAT polytime reduces to all of these problems (and many, many more) 2 3SAT polytime reduces to INDEPENDENTSET8. INTRACTABILITY II P vs. NP ‣ NPcomplete ‣ coNP ‣ NPhard ‣Decision problems Decision problem. Problem X is a set of strings. Instance s is one string. Algorithm A solves problem X: A(s) = yes iff s ∈ X. 
 Def. Algorithm A runs in polynomial time if for every string s, A(s) terminates in at most p( s ) "steps", where p(⋅) is some polynomial function. 
 length of s 
 
 Ex. Problem PRIMES = 2, 3, 5, 7, 11, 13, 17, 23, 29, 31, 37, …. . Instance s = 592335744548702854681. 8 AKS algorithm: solves PRIMES in O( s ) steps. 4Definition of P P. Decision problems for which there is a polytime algorithm. Problem Description Algorithm yes no gradeschool 51, 17 51, 16 MULTIPLE Is x a multiple of y division Euclid (300 BCE) 34, 39 34, 51 RELPRIME Are x and y relatively prime AKS (2002) 53 51 PRIMES Is x prime Is the edit distance between dynamic niether acgggt EDITDISTANCE neither ttttta programming x and y less than 5 " " 0 1 1 4 1 0 0 1 GaussEdmonds Is there a vector x that ( ( ' ' 2 4 −2 , 2 1 1 1 , 1 LSOLVE ( ( ' ' elimination satisfies Ax = b ( ( ' ' 0 3 15 36 0 1 1 1 ' ' Is an undirected graph
 depthfirst search € € UCONN G connected (Theseus) 5NP Certification algorithm intuition. Certifier views things from "managerial" viewpoint. Certifier doesn't determine whether s ∈ X on its own;
 rather, it checks a proposed proof t that s ∈ X. 
 Def. Algorithm C(s, t) is a certifier for problem X if for every string s,
 s ∈ X iff there exists a string t such that C(s, t) = yes. 
 "certificate" or "witness" 
 Def. NP is the set of problems for which there exists a polytime certifier. C(s, t) is a polytime algorithm. Certificate t is of polynomial size: t ≤ p( s ) for some polynomial p(⋅). 
 
 Remark. NP stands for nondeterministic polynomial time. 6Certifiers and certificates: composite COMPOSITES. Given an integer s, is s composite 
 Certificate. A nontrivial factor t of s. Such a certificate exists iff s is composite. Moreover t ≤ s . 
 Certifier. Check that 1 t s and that s is a multiple of t. 
 
 
 instance s 437669 
 437,669 = 541 × 809 certificate t 541 or 809 
 
 
 
 in fact, COMPOSITES ∈ P Conclusion. COMPOSITES ∈ NP. 7Certifiers and certificates: satisfiability SAT. Given a CNF formula Φ, does it have a satisfying truth assignment 3SAT. SAT where each clause contains exactly 3 literals. 
 Certificate. An assignment of truth values to the Boolean variables. 
 Certifier. Check that each clause in Φ has at least one true literal. 
 
 
 instance s Φ = x ∨ x ∨ x ∧ x ∨ x ∨ x ∧ x ∨ x ∨ x 
 ( ) ( ) ( ) 1 2 3 1 2 3 1 2 4 
 certificate t x = true, x = true, x = false, x = false 1 2 3 4 
 € 
 
 
 
 Conclusions. SAT ∈ NP, 3SAT ∈ NP. 8Certifiers and certificates: Hamilton path HAMPATH. Given an undirected graph G = (V, E), does there exist a simple path P that visits every node 
 Certificate. A permutation of the n nodes. 
 Certifier. Check that the permutation contains each node in V exactly once, and that there is an edge between each pair of adjacent nodes. 
 
 
 
 
 
 
 certificate t instance s 
 Conclusion. HAMPATH ∈ NP. 9Definition of NP NP. Decision problems for which there is a polytime certifier. Problem Description Algorithm yes no " " 0 1 1 4 1 0 0 1 Gauss–Edmonds Is there a vector x
 ( ( ' ' 2 4 −2 , 2 1 1 1 , 1 LSOLVE ( ( ' ' elimination that satisfies Ax = b ( ( ' ' 0 3 15 36 0 1 1 1 ' ' € € COMPOSITES AKS (2002) 51 53 Is x composite Does x have a nontrivial factor FACTOR (56159, 50) (55687, 50) less than y ¬ x ∨ ¬ x ∨ ¬ x ¬ x ∨ ¬ x 1 2 3 1 2 Given a CNF formula, does it have SAT ¬ x ∨ ¬ x ∨ ¬ x ¬ x ∨ ¬ x 1 2 3 1 2 a satisfying truth assignment ¬ x ∨ ¬ x ∨ ¬ x ¬ x ∨ ¬ x 1 2 3 1 2 Can the nodes of a graph G
 3COLOR be colored with 3 colors Is there a simple path between
 HAMPATH u and v that visits every node 10Definition of NP NP. Decision problems for which there is a polytime certifier. “ NP captures vast domains of computational, scientific, and mathematical
 endeavors, and seems to roughly delimit what mathematicians and scientists
 have been aspiring to compute feasibly. ” — Christos Papadimitriou “ In an ideal world it would be renamed P vs VP. ” — Clyde Kruskal 11P, NP, and EXP P. Decision problems for which there is a polytime algorithm. NP. Decision problems for which there is a polytime certifier. EXP. Decision problems for which there is an exponentialtime algorithm. 
 Claim. P ⊆ NP. Pf. Consider any problem X ∈ P. By definition, there exists a polytime algorithm A(s) that solves X. Certificate t = ε, certifier C(s, t) = A(s). ▪ 
 Claim. NP ⊆ EXP. Pf. Consider any problem X ∈ NP. By definition, there exists a polytime certifier C(s, t) for X,
 where certificate t satisfies t ≤ p( s ) for some polynomial p(⋅). To solve input s, run C(s, t) on all strings t with t ≤ p( s ). Return yes if C(s, t) returns yes for any of these potential certificates. ▪ 
 Remark. Timehierarchy theorem implies P ⊊ EXP. 12The main question: P vs. NP Q. How to solve an instance of 3SAT with n variables n A. Exhaustive search: try all 2 truth assignments. 
 Q. Can we do anything substantially more clever Conjecture. No polytime algorithm for 3SAT. "intractable" 13The main question: P vs. NP Does P = NP Cook 1971, Edmonds, Levin, Yablonski, Gödel
 Is the decision problem as easy as the certification problem 
 
 
 NP EXP EXP 
 P 
 P = NP 
 
 
 If P ≠ NP If P = NP 
 
 If yes. Efficient algorithms for 3SAT, TSP, 3COLOR, FACTOR, … If no. No efficient algorithms possible for 3SAT, TSP, 3COLOR, … 
 Consensus opinion. Probably no. 14Possible outcomes P ≠ NP. “ I conjecture that there is no good algorithm for the traveling salesman problem. My reasons are the same as for any mathematical conjecture: (i) It is a legitimate mathematical possibility and (ii) I do not know.” — Jack Edmonds 1966 15Possible outcomes P ≠ NP. “ In my view, there is no way to even make intelligent guesses about the answer to any of these questions. If I had to bet now, I would bet that P is not equal to NP. I estimate the halflife of this problem at 25–50 more years, but I wouldn’t bet on it being solved before 2100. ” — Bob Tarjan (2002) “ We seem to be missing even the most basic understanding of the nature of its difficulty…. All approaches tried so far probably (in
 some cases, provably) have failed. In this sense P =NP is different from many other major mathematical problems on which a gradual progress was being constantly done (sometimes for centuries) whereupon they yielded, either completely or partially. ” — Alexander Razborov (2002) 16Possible outcomes P = NP. “ I think that in this respect I am on the loony fringe of the mathematical community: I think (not too strongly) that P=NP and this will be proved within twenty years. Some years ago, Charles Read and I worked on it quite bit, and we even had a celebratory dinner in a good restaurant before we found an absolutely fatal mistake. ”
 — Béla Bollobás (2002) 17Other possible outcomes 100 P = NP, but only Ω(n ) algorithm for 3SAT. 
 logn P ≠ NP, but with O(n ) algorithm for 3SAT. 
 P = NP is independent (of ZFC axiomatic set theory). “ It will be solved by either 2048 or 4096. I am currently somewhat pessimistic. The outcome will be the truly worst case scenario: namely that someone will prove “P = NP because there are only finitely many obstructions to the opposite hypothesis”; hence there exists a polynomial time solution to SAT but we will never know
 its complexity ” — Donald Knuth 18Millennium prize Millennium prize. 1 million for resolution of P = NP problem. 19Looking for a job Some writers for the Simpsons and Futurama. J. Steward Burns. M.S. in mathematics (Berkeley '93). David X. Cohen. M.S. in computer science (Berkeley '92). Al Jean. B.S. in mathematics. (Harvard '81). Ken Keeler. Ph.D. in applied mathematics (Harvard '90). Jeff Westbrook. Ph.D. in computer science (Princeton '89). Copyright © 1990, Matt Groening Copyright © 2000, Twentieth Century Fox 20Princeton CS Building, West Wall, Circa 2001 21Princeton CS Building, West Wall, Circa 2001 1 0 1 0 0 0 1 0 1 0 1 1 0 1 0 0 1 1 1 1 0 1 1 0 0 0 0 1 1 0 0 1 1 1 1 char ASCII binary P 80 1010000 = 61 0111101 N 78 1001110 P 80 1010000 63 0111111 228. INTRACTABILITY II P vs. NP ‣ NPcomplete ‣ coNP ‣ NPhard ‣Polynomial transformation Def. Problem X polynomial (Cook) reduces to problem Y if arbitrary instances of problem X can be solved using: Polynomial number of standard computational steps, plus Polynomial number of calls to oracle that solves problem Y. 
 Def. Problem X polynomial (Karp) transforms to problem Y if given any input x to X, we can construct an input y such that x is a yes instance of X
 iff y is a yes instance of Y. we require y to be of size polynomial in x 
 
 Note. Polynomial transformation is polynomial reduction with just one call to oracle for Y, exactly at the end of the algorithm for X. Almost all previous reductions were of this form. Open question. Are these two concepts the same with respect to NP we abuse notation ≤ and blur distinction p 24NPcomplete NPcomplete. A problem Y ∈ NP with the property that for every
 problem X ∈ NP, X ≤ Y. p 
 Theorem. Suppose Y ∈ NPcomplete. Then Y ∈ P iff P = NP. Pf. ⇐ If P = NP, then Y ∈ P because Y ∈ NP. Pf. ⇒ Suppose Y ∈ P. Consider any problem X ∈ NP. Since X ≤ Y, we have X ∈ P. p This implies NP ⊆ P. We already know P ⊆ NP. Thus P = NP. ▪ 
 
 
 
 Fundamental question. Do there exist "natural" NPcomplete problems 25Circuit satisfiability CIRCUITSAT. Given a combinational circuit built from AND, OR, and NOT gates, is there a way to set the circuit inputs so that the output is 1 output ∧ ∧ ¬ yes: 1 0 1 ∧ ∨ ∨ 1 0 variable inputs hardcoded inputs 26The "first" NPcomplete problem Theorem. CIRCUITSAT ∈ NPcomplete. Cook 1971, Levin 1973 The Complexity of TheoremProving Procedures IX 1973 . 3 Stephen A. Cook University of Toronto Summary certain recursive set of strings on this alphabet, and we are interested 519.14 It is shown that any recognition in the problem of finding a good problem solved by a polynomial time lower bound on its possible recog bounded nondeterministic Turing nition times. We provide no such » . machine can be "reduced" to the pro lower bound here, but theorem 1 will blem of determining whether a given give evidence that tautologies is propositional formula is a tautology. a difficult set to recognize, since « » , Here "reduced" means, roughly speak many apparently difficult problems , ing, that the first problem can be can be reduced to determining tau . solved deterministically in polyno tologyhood. By reduced we mean, mial time provided an oracle is roughly speaking, that if tauto available for solving the second. logyhood could be decided instantly ( , From this notion of reducible, (by an "oracle") then these problems , , ). polynomial degrees of difficulty are could be decided in polynomial time. . defined, and it is shown that the In order to make this notion precise, , problem of determining tautologyhood we introduce query machines, which . has the same polynomial degree as the are like Turing machines with oracles : , , problem of determining whether the in I. . first of two given graphs is iso , . morphic to a subgraph of the second. A query machine is a multitape , Other examples are discussed. A Turing machine with a distinguished . 1,2 method of measuring the complexity of tape called the query tape, and ( ), proof procedures for the predicate three distinguished states called . ( , , , .) calculus is introduced and discussed. the query state, yes state, and n.o , ( state, respectively. If M is a ) , Throughout this paper, a set of query machine and T is a set of ( ) , , strings means a set of strings on strings, then a Tcomputation of M « » ( some fixed, large, finite alphabet Z. is a computation of M in which , .). This alphabet is large enough to in initially M is in the initial . clude symbols for all sets described state and has an input string w on fn) gn) , here. All Turing machines are deter its input tape, and each time M f(n) (g(n)+2) g(n) (f(n) +2). ministic recognition devices, unless assumes the query state there is a the contrary is explicitly stated. string u on the query tape, and « ». the next state M assumes is the . ( ) i. Tautologies and Polynomial Re yes state if uET and the no state « , , , ( , )», ( , ) — , Reducibility. if uT. We think of an "oracle", , . ( which knows T, placing M in the , , — Let us fix a formalism for yes state or no state. , ; , ). the propositional calculus in , . which formulas are written as . strings on I. Since we will re Definition . quire infinitely many proposition , . symbols (atoms), each such symbol A set S of strings is Predu 1. 500 will consist of a member of Z cible (P for polynomial) to a set . ( followed by a number in binary T of strings iff there is some ). notation to distinguish that 2. . query machine M and a polynomial , symbol. Thus a formula of length Q(n) such that for each input string ( ). n can only have about n/logn w, the Tcomputation of M with in 3. , distinct function and predicate put w halts within Q(Iwl) steps . ( , , .) symbols. The logical connectives (lwl is the length of w and ends 4. . ( are (and), v (or), and (not). in an accepting state iff wcS. ). 5. . ( ). The set of tautologies It is not hard to see that 6. 1 100 (denoted by tautologies) is a Preducibility is a transitive re , lation. Thus the relation E on . . 151 27The "first" NPcomplete problem Theorem. CIRCUITSAT ∈ NPcomplete. Pf sketch. Clearly, CIRCUITSAT ∈ NP. Any algorithm that takes a fixed number of bits n as input and
 produces a yes or no answer can be represented by such a circuit. Moreover, if algorithm takes polytime, then circuit is of polysize.
 
 sketchy part of proof; fixing the number of bits is important,
 
 and reflects basic distinction between algorithms and circuits Consider any problem X ∈ NP. It has a polytime certifier C(s, t),
 where certificate t satisfies t ≤ p( s ) for some polynomial p(⋅). View C(s, t) as an algorithm with s + p( s ) input bits and convert it
 into a polysize circuit K. first s bits are hardcoded with s remaining p( s ) bits represent (unknown) bits of t Circuit K is satisfiable iff C(s, t) = yes. 28Example Ex. Construction below creates a circuit K whose inputs can be set so that it outputs 1 iff graph G has an independent set of size 2. independent set of size 2 ∧ independent set ¬ both endpoints of some ∨ edge have been chosen ∨ set of size 2 ∨ ∧ ∧ ∧ ∨ u ∧ ∧ ∧ v w G = (V, E), n = 3 uw uv vw u v w 1 0 1 n inputs hardcoded inputs " n ' (nodes in independent set) 2 (graph description) 29 € Establishing NPcompleteness Remark. Once we establish first "natural" NPcomplete problem,
 others fall like dominoes. 
 Recipe. To prove that Y ∈ NPcomplete: Step 1. Show that Y ∈ NP. Step 2. Choose an NPcomplete problem X. Step 3. Prove that X ≤ Y. p 
 
 Theorem. If X ∈ NPcomplete, Y ∈ NP, and X ≤ Y, then Y ∈ NPcomplete. p Pf. Consider any problem W ∈ NP. Then, both W ≤ X and X ≤ Y. p p By transitivity, W ≤ Y. p by definition of
 by assumption Hence Y ∈ NPcomplete. ▪ NPcomplete 303satisfiability is NPcomplete Theorem. 3SAT ∈ NPcomplete. Pf. Suffices to show that CIRCUITSAT ≤ 3SAT since 3SAT ∈ NP. P Given a combinational circuit K, we construct an instance Φ of 3SAT
 that is satisfiable iff the inputs of K can be set so that it outputs 1. 313satisfiability is NPcomplete Construction. Let K be any circuit.
 Step 1. Create a 3SAT variable x for each circuit element i.
 i Step 2. Make circuit compute correct values at each node: x = ¬ x ⇒ add 2 clauses: x ∨ x , x ∨ x 2 3 2 3 2 3 x = x ∨ x ⇒ add 3 clauses: 1 4 5 x ∨ x , x ∨ x , x ∨ x ∨ x 1 4 1 5 1 4 5 x = x ∧ x ⇒ add 3 clauses:
 0 1 2 x ∨x , x ∨x , x ∨ x ∨ x 0 1 0 2 0 1 2 € € Step 3. Hardcoded input values and output value. x 0 € x = 0 ⇒ add 1 clause: 5 x 5 ∧ x x = 1 ⇒ add 1 clause: 0 0 x x ∨ 1 2 ¬ € € x x x 5 4 3 0 323satisfiability is NPcomplete Construction. continued
 Step 4. Turn clauses of length 1 or 2 into clauses of length 3. Create four new variables z , z , z , and z . 1 2 3 4 Add 8 clauses to force z = z = 0:
 1 2 
 (z z z ), (z z z ), (z z z ), (z z z ) 1 3 4 1 3 4 1 3 4 1 3 4 
 (z z z ), (z z z ), (z z z ), (z z z ) 2 3 4 2 3 4 2 3 4 2 3 4 Replace any clause with a single term ( t ) with ( t ∨ z ∨ z ). i i 1 2 Replace any clause with two terms ( t ∨ t ) with ( t ∨ t ∨ z ). i j i j 1 333satisfiability is NPcomplete Lemma. Φ is satisfiable iff the inputs of K can be set so that it outputs 1.
 
 Pf. ⇐ Suppose there are inputs of K that make it output 1. Can propagate input values to create values at all nodes of K. This set of values satisfies Φ. 
 Pf. ⇒ Suppose Φ is satisfiable. We claim that the set of values corresponding to the circuit inputs constitutes a way to make circuit K output 1. The 3SAT clauses were designed to ensure that the values
 assigned to all node in K exactly match what the circuit
 x 0 would compute for these nodes. ▪ ∧ x x ∨ 1 2 ¬ x x x 5 4 3 0 34Implications of Karp CIRCUITSAT 
 3SAT INDEPENDENTSET DIRHAMCYCLE GRAPH3COLOR SUBSETSUM VERTEXCOVER SCHEDULING HAMCYCLE PLANAR3COLOR CIRCUITSAT polytime reduces to all of SETCOVER TSP these problems (and many, many more) 35 3SAT polytime reduces to INDEPENDENTSETImplications of CookLevin CIRCUITSAT 
 
 3SAT INDEPENDENTSET DIRHAMCYCLE GRAPH3COLOR SUBSETSUM VERTEXCOVER SCHEDULING HAMCYCLE PLANAR3COLOR All of these problems (and many, many more) SETCOVER TSP polytime reduce to CIRCUITSAT. 36 INDEPENDENTSET polytime reduces to CIRCUITSATImplications of Karp + CookLevin CIRCUITSAT 
 3SAT 
 INDEPENDENTSET DIRHAMCYCLE GRAPH3COLOR SUBSETSUM VERTEXCOVER SCHEDULING HAMCYCLE PLANAR3COLOR All of these problems are NPcomplete; they are SETCOVER TSP manifestations of the same really hard problem. 37 3SAT and INDEPENDENTSET polytime reduce to one anotherSome NPcomplete problems Basic genres of NPcomplete problems and paradigmatic examples. Packing + covering problems: SETCOVER, VERTEXCOVER,INDEPENDENTSET. Constraint satisfaction problems: CIRCUITSAT, SAT, 3SAT. Sequencing problems: HAMCYCLE, TSP. Partitioning problems: 3DMATCHING, 3COLOR. Numerical problems: SUBSETSUM, PARTITION. Practice. Most NP problems are known to be either in P or NPcomplete. 
 Notable exceptions. FACTOR, GRAPHISOMORPHISM, NASHEQUILIBRIUM. 
 Theorem. Ladner 1975 Unless P = NP, there exist problems in NP that are neither in P nor NPcomplete. 38More hard computational problems Garey and Johnson. Computers and Intractability. Appendix includes over 300 NPcomplete problems. Most cited reference in computer science literature. 39More hard computational problems Aerospace engineering. Optimal mesh partitioning for finite elements. Biology. Phylogeny reconstruction. Chemical engineering. Heat exchanger network synthesis. Chemistry. Protein folding. Civil engineering. Equilibrium of urban traffic flow. Economics. Computation of arbitrage in financial markets with friction. Electrical engineering. VLSI layout. Environmental engineering. Optimal placement of contaminant sensors. Financial engineering. Minimum risk portfolio of given return. Game theory. Nash equilibrium that maximizes social welfare. Mathematics. Given integer a , …, a , compute 1 n Mechanical engineering. Structure of turbulence in sheared flows. Medicine. Reconstructing 3d shape from biplane angiocardiogram. Operations research. Traveling salesperson problem. Physics. Partition function of 3d Ising model. Politics. Shapley–Shubik voting power. Recreation. Versions of Sudoku, Checkers, Minesweeper, Tetris. Statistics. Optimal experimental design. 40Extent and impact of NPcompleteness Extent of NPcompleteness. Papadimitriou 1995 Prime intellectual export of CS to other disciplines. 6,000 citations per year (more than "compiler", "OS", "database"). Broad applicability and classification power. 
 NPcompleteness can guide scientific inquiry. 1926: Ising introduces simple model for phase transitions. 1944: Onsager finds closedform solution to 2DISING in tour de force. 19xx: Feynman and other top minds seek solution to 3DISING. 2000: Istrail proves 3DISING ∈ NPcomplete. a holy grail of statistical mechanics search for closed formula appears doomed 41P vs. NP revisited Overwhelming consensus (still). P ≠ NP. 
 
 NP 
 P = NP P 
 NPC 
 
 P ≠ NP P = NP 
 
 Why we believe P ≠ NP. “ We admire Wiles' proof of Fermat's last theorem, the scientific theories of Newton, Einstein, Darwin, Watson and Crick, the design of the Golden Gate bridge and the Pyramids, precisely because they seem to require a leap which cannot be made by everyone, let alone by a simple mechanical device. ” — Avi Wigderson 42You NPcomplete me 438. INTRACTABILITY II P vs. NP ‣ NPcomplete ‣ coNP ‣ NPhard ‣Asymmetry of NP Asymmetry of NP. We need short certificates only for yes instances. 
 Ex 1. SAT vs. UNSAT. Can prove a CNF formula is satisfiable by specifying an assignment. How could we prove that a formula is not satisfiable SAT. Given a CNF formula Φ, is there a satisfying truth assignment UNSAT. Given a CNF formula Φ, is there no satisfying truth assignment 45Asymmetry of NP Asymmetry of NP. We need short certificates only for yes instances. 
 Ex 2. HAMCYCLE vs. NOHAMCYCLE. Can prove a graph is Hamiltonian by specifying a permutation. How could we prove that a graph is not Hamiltonian HAMCYCLE. Given a graph G = (V, E), is there a simple cycle Γ that contains every node in V NOHAMCYCLE. Given a graph G = (V, E), is there no simple cycle Γ that contains every node in V 46Asymmetry of NP Asymmetry of NP. We need short certificates only for yes instances. 
 Q. How to classify UNSAT and NOHAMCYCLE SAT ∈ NPcomplete and SAT ≡ UNSAT. P HAMCYCLE ∈ NPcomplete and HAMCYCLE ≡ NOHAMCYCLE. P But neither UNSAT nor NOHAMCYCLE are known to be in NP. 47NP and coNP NP. Decision problems for which there is a polytime certifier. Ex. SAT, HAMCYCLE, and COMPOSITES. 
 Def. Given a decision problem X, its complement X is the same problem with the yes and no answers reversed. 
 Ex. X = 4, 6, 8, 9, 10, 12, 14, 15, … 
 ignore 0 and 1
 (neither prime nor composite) X = 2, 3, 5, 7, 11, 13, 17, 23, 29, … 
 
 coNP. Complements of decision problems in NP.
 Ex. UNSAT, NOHAMCYCLE, and PRIMES. 48NP = coNP Fundamental open question. Does NP = coNP Do yes instances have succinct certificates iff no instances do Consensus opinion: no. 
 Theorem. If NP ≠ coNP, then P ≠ NP. Pf idea. P is closed under complementation. If P = NP, then NP is closed under complementation. In other words, NP = coNP. This is the contrapositive of the theorem. 49Good characterizations Good characterization. Edmonds 1965 NP ∩ coNP. If problem X is in both NP and coNP, then: for yes instance, there is a succinct certificate for no instance, there is a succinct disqualifier Provides conceptual leverage for reasoning about a problem. 
 Ex. Given a bipartite graph, is there a perfect matching If yes, can exhibit a perfect matching. If no, can exhibit a set of nodes S such that neighbors(S) S . JOURNAL OF RESEARCH of the National Bureau of StandardsB. Mathematics and Mathematical Physics Vol. 69B, Nos. 1 and 2, JanuaryJune 1965 Minimum Partition of a Matroid Into Independent Subsets Jack Edmonds (December 1, 1964) A matroid M is a finite set M of ele ments with a famil y of subsets, called independent, such th at (I) every subset of an independe nt set is independent, and (2) for e ve ry subset A of M , all maximal indepe nde nt subsets of A have the sa me cardinality, called the rank r\A) of A. It is proved that a matroid can be partitioned into as few as k sets, each inde pende nt , if and only if every subse t A has cardinality at most k . r(A ). wh ic h has exactly two ones in each column. The 50 1.0. Introduction columns are the edges of the graph and the rows are Matroids can be regarded as a certain abstraction the nodes of the grap h. An edge and a node are said of matrices 8.2 They represent the properties of to meet if there is a one located in that column and matrices whic h are invariant under ele me ntary row that row. Of course a grap h can also be regarded operations but whic h are not invariant under ele men vi sually as a geometric netwo rk . It is often helpful tary column operations namely properties of depend to visualize state ments on matroids for the case of ence among the column s For any matrix over any graphs, though it can be misleadin g. Matroids do field, there is a matroid whose elements correspond not contain objects correspondin g to nodes or rows . to the columns of the matrix and whose independent Theorem 1 on "minimum partitions," the subject of , sets of ele ments correspond to the linearly inde pendent this paper, was discovered in the process of unifying sets of columns A matroid M is completely deter results described in the next paper, " On Lehman's mined by its elements and its independent sets of Switching Game and a Theorem of Tutte and Nash ele ments. Williams" (denoted here as "Part II"), which is a direct The same letter will be used to denote a matroid sequel. Theore m 1 is shown there to be closely re and its set of elements. The letter I with various sub lated to those res ults. Lately, I have learned that or superscripts will be used to denote an independent Theorem 1 for the case of graphs (see sec. 1.7) was set. anticipated by Nas hWilliams 5. The interest of matroids does not lie only in how they By borrowing from work of others, I intend that this generalize some known theorems of linear algebra. paper together with possible seq uels be partly exposi There are examples, which I shall report elsewhere, tory and technically almost selfcontained. of matroids whic h do not arise from any matrix over any field so matroid theory does truly generalize an 1.1. The Problem aspect of matrices. However, matroid theory is jus tified by new problems in matrix theory itself in fact Various aspects of matroids in particular, the first by problems in the special matrix theory of graphs pair of axioms we cite hold intrin sic interest which , (networks). It happens that an axiomatic matroid set is quite separate from linear algebra. ting is most natural for viewing these proble ms and that AXIOM 1: Every subset of an independent set of matrix machinery is clumsy and superfluous for view elements is independent. ing them. The situation is somewhat similar to the Any finite collection of elements and family of so superfluity of (real) matrices to the theory of linear op called independent sets of these ele ments whic h satis erators, though there a quite different aspect of mat fies axiom 1 we shall call an independe nce syste m. rices is superfluous. When it comes to implementing This also happens to be the definiti on of an abstract either theory, matrices are often the way to do it. simplicial complex, though the topology of complexes will not concern us Matroid theory so far has been motivated mainly It is easy to describe implicitly large independe nce by graphs, a special class of matrices. A graph G may systems which are apparently very unwieldy to an be regarded as a matrixN(G) of zeroes and ones, mod 2, alyze. First example: given a graph G, defin e an independent set of nodes in G to be such that no edge I Sponsored by the Ar my Researc h Office (Durham), Presented at the Seminar on Malroids, Nat ional Bureau of Standards, Au g. 3JSept. 11, 1964. I am much inde bted of G meets two nodes of the set. Second example : 10 Alfred Lehman for e ncouraging my interest in the subjec t. Z Figures in brackets ind icate the references at the end of thi s pape r. define an independent set of edges in G to be such th at 67 1.2. Ground Rules no node meets two edges of the set. Third example: define an independent set of edges in G to be such that One is tempted to surmise that a minimum coloring the edges of the set, as column vectors of N(G), are can be effected for a system by some simple process linearly independent. The third example is the pro like extracting a maximal independent set to take on totype of the systems we shall study here. the first color, then extracting a maximal independent A minimum coloring of the nodes of a graph G is a set of what is left to take on the second color, and so partition of the nodes into as few sets (colors) as pos on till all elements are colored. This is usually far sible so that each set is independent. A good char from being successful even for matroids, though it acterization of the minimum colorings of the nodes in is precisely matroids for which a similar sort of mono a graph is unknown (unless the graph is bipartite, i.e., tonic procedure always yields a maximum cardinality the nodes can be colored with two colors). To find independent set and, as we shall see, in another paper, one would undoubtedly settle the "four color" also always yields a maximum weightsum independent conjecture. set when the elements carry arbitrary real weights. A problem closely related to minimum coloring is Consider the class of matroids implicit in the class the "packing problem." That is to find a good char MF of all matrices over fields of integers modulo primes. acterization (and an algorithm) for maximum cardinal (For large enough prime, this class includes the ity independent sets. More generally the "weighted matroid of any matrix over the rational field.) We packing problem" is, where each element of the system seek a good algorithm for partitioning the columns carries a real numerical weight, to characterize the (elements of the matroid) of anyone of the matrices independent sets whose weightsums are maximum. (matroids) into as few sets as possible so that each set The packing problem for the systems of the first is independent. Of course, by carrying out the mono example is also very much unsolved (unless the graph tonic coloring procedure described above in all possible is bipartite). ways for a given matrix, one can be assured of encoun The minimum coloring problem for the systems of tering such a partition for the matrix, but this would the second example is unsolved (unless the graph is entail a horrendous amount of work. We seek an al bipartite). Its solution would also undoubtedly set gorithm for which the work involved increases only tle the fourcolor conjecture. However the packing algebraically with the size of the matrix to which it is problem, and more generally the weighted packing Good characterizations applied, where we regard the size of a matrix as in problem, is solved for the second example by the ex creasing only linearly with the number of columns, tensive theory of "matchings in graphs." the number of rows, and the characteristic of the field. For the third example the packing problem is in a As in most combinatorial problems, finding a finite sense trivial. It is well known that the system of algorithm is trivial but finding an algorithm which linearly independent sets of edges in a graph, and meets this condition for practical feasibility is not more generally the system of linearly independent trivial. sets of columns in a matrix, satisfies the following: We seek a good characterization of the minimum AXIOM 2: For any subset A of the elements, all maxi number of independent sets into which the columns mal independent sets contained in A contain the same of a matrix of Mr can be partitioned. As the criterion number of elements. of "good" for the characterization we apply the "prin ciple of the absolute supervisor." The good charac A matroid is a (finite) system of elements and sets terization will describe certain information about the of elements which satisfies axioms I and 2. matrix which the supervisor can require his assistant For any independence system, any subsystem con to search out along with a minimum partition and sisting of a subset A of the elements and all of the which the supervisor can then use with ease to verify independent sets contained in A is an independence with mathematical certainty that the partition is in system. Thus, a matroid is an independence system deed minimum. Having a good characterization does where the packing problem is postulated to be trivial not mean necessarily that there is a good algorithm. for the system and all of its subsystems. For me, hav The assistant might have to kill himself with work to ing spent much labor on packing problems, it is find the information and the partition. pleasant to study such systems. Matroids have a Theorem 1 on partitioning matroids provides the surprising richness of structure, as even the special good characterization in the case of matrices of Mr. case of graphic matroids shows. The proof of the theorem yields a good algorithm in Clearly, a subsystem of a matroid M is a matroid. the case of matrices of Mr. (We will not elaborate on We call it a submatroid and we use the same symbol 51 how.) The theorem and the proof apply as well to to denote it and its set of elements. The rank, rCA), all matroids via the matroid axioms. However, the of a set A of elements in M or the rank, rCA), of the "goodness" for matrices depends on being able to submatroid A of M is the number of elements in each carry out constructively with ease those matrix opera maximal independent set contained in A, i.e ., the num tions which correspond to the existential assertions ber of elements in a bas e of A. of the theory. A fundamental problem of matroid The main result of this paper is a solution of the theory is to find a good representation for general minimum coloring problem for the independent sets matroids good perhaps relative to the rank and the of a matroid. Another paper will treat the weighted number of elements in the matroids. There is a very packing problem for matroids. 68 Good characterizations Observation. P ⊆ NP ∩ coNP. Proof of maxflow mincut theorem led to stronger result that maxflow and mincut are in P. Sometimes finding a good characterization seems easier than finding an efficient algorithm. 
 Fundamental open question. Does P = NP ∩ coNP Mixed opinions. Many examples where problem found to have a nontrivial good characterization, but only years later discovered to be in P. 52Linear programming is in NP ∩ coNP m×n m n LINEARPROGRAMMING. Given A ∈ ℜ , b ∈ ℜ , c ∈ ℜ , and α ∈ ℜ, does there n T exist x ∈ ℜ such that Ax ≤ b, x ≥ 0 and c x ≥ α 
 Theorem. GaleKuhnTucker 1948 LINEARPROGRAMMING ∈ NP ∩ coNP. Pf sketch. If (P) and (D) are nonempty, then max = min. T T (P) maxc x (D) miny b T s. t. Ax ≤ b s. t. A y ≥ c x ≥ 0 y ≥ 0 € € 53Linear programming is in NP ∩ coNP m×n m n LINEARPROGRAMMING. Given A ∈ ℜ , b ∈ ℜ , c ∈ ℜ , and α ∈ ℜ, does there n T exist x ∈ ℜ such that Ax ≤ b, x ≥ 0 and c x ≥ α 
 Theorem. Khachiyan 1979 LINEARPROGRAMMING ∈ P. 1980 , 1 20 519.852 . . ( ) , . m 2 2 .. ., x ..., : h (0.1) (1 1 ;..+ , i=l , 2,... , , a b. i h L = uii log2 (1 bi 1+1 + log2 (0.2) + 1 L O G 2 ( 1 1 + 1 ) + 2J Yi 54 , . . 0 1, . § 1—4 L n R (0.1). 2 0 ( + ) , O ( L ) . 3 0 (n (n+m)L ) + , —, X, : , , max, (L) . , , n R 2 . 3 1. , 3 2 0(n (n +m)L) ( ) 2 0( + ) . , , 3 : (L) . § 5 , § 1—4, , a bi. i h . Primality testing is in NP ∩ coNP Theorem. Pratt 1975 PRIMES ∈ NP ∩ coNP. SIAM J. COMPUT. Vol. 4, No. 3, September 1975 EVERY A SUCCINCT CERTIFICATE PRIME HAS VAUGHAN R. PRATTf To a n it suffices exhibit the for the Abstract. prove that number iscomposite, to working multiplica tion of a pair of This working, represented as a, string, is of length bounded by a polynomial factors. We for the It in log n. show that the same property holds primes. is noteworthy that almost no other set is known to have the property thatshort proofs for membership or exist for all nonmembership candidates without known to have the being property that such proofs are easy to come by. It remains an open problem whether a prime n can be in of recognized only log n operations a Turing machine for fixed any The proof system used for is as follows. certifying primes AXIOM. (x, y, 1). INFERENCE RULES. tp 1)/q (p, x, a), q (p, x, qa) provided x and (mod p) ql(P 1). R1 p , (p,x,p 1)p providedx (modp). R2: THEOREM 1. p is a theorem p is a prime. THEOREM 2. a a p is theorem p has proof 4 log p lines. of words, Key primes, membership, nondeterministic, proof,NPcomplete, computational complexity tell 1. Proofs. We know of no efficient method that will reliably whether method a givennumber isprime or composite.By "efficient",wemean a forwhich the time is at most a polynomial in the length of the number written in 55 positional notation. Thus the cost of testing primes and composites is very high. In contrast, the cost ofselling composites (persuading a potential customer that you have one) is lowin one suffices. The catch is that the very every case, multiplication only work to his short the effort salesman may need to overtime prepare sales pitch; is nevertheless rewarded when there are many customers. At a of the Mathematical in Frank Cole meeting American Society 1903, used this of to add dramatic to the presentation of property composites impact his Hisresultwasthat267 1was atwocenturies paper. composite,contradicting old conjecture ofMersenne. Although it had taken Cole "three years ofSundays" to find the factors, once he had done so he in a few minutes and without could, a uttering word, convince a large audience of his result simply by writing down x the arithmetic for evaluating 267 and 193707721 761838257287. We now show that the primes are to a lesser extent similarly blessed; one may certify p with a proof of at most 4 log2 p lines, in a system each ofwhose 3 time The method is based on the inference rules are readily applied in O(log p). LucasLehmer heuristic for testing primeness. (Lehmer (1927)) In the to be theorems take one oftwo forms: system described, "p", is or (i) asserting.that p prime, "(p, that we are towards establishing (ii) x, a)", asserting making progress that is a and that x is a root p); a is a progress indicator p prime primitive (mod Received by the editors May 24, 1974. Project MAC Massachusetts Institute of Technology, Cambridge, Massachusetts 02139. This f research was the National Science supported by Foundation under Grant GJ34671. a similar Edmonds (1965) discusses situation with a "supervisor and his assistant". hardworking 214Primality testing is in NP ∩ coNP Theorem. Pratt 1975 PRIMES ∈ NP ∩ coNP. Pf sketch. An odd integer s is prime iff there exists an integer 1 t s s.t. s−1 t ≡ 1 (mods) (s−1) /p t ≠ 1 (mods) for all prime divisors p of s1 € CERTIFIER (s) instance s 437677 2 certificate t 17, 2 × 3 × 36473 CHECK s – 1 = 2 × 2 × 3 × 36473. s–1 CHECK 17 = 1 (mod s). prime factorization of s–1
 (s–1) / 2 CHECK 17 ≡ 437676 (mod s). also need a recursive certificate
 (s–1) / 3 to assert that 3 and 36,473 are prime CHECK 17 ≡ 329415 (mod s). (s–1) / 36,473 CHECK 17 ≡ 305452 (mod s). use repeated squaring 56Primality testing is in P Theorem. AgrawalKayalSaxena 2004 PRIMES ∈ P. Annals of Mathematics, 160 (2004), 781–793 Annals of Mathematics, 160 (2004), 781–793 PRIMES is in P By Manindra Agrawal, Neeraj Kayal, and Nitin Saxena PRIMES is in P Abstract By Manindra Agrawal, Neeraj Kayal, and Nitin Saxena Wepresentanunconditionaldeterministicpolynomialtimealgorithmthat determines whether an input number is prime or composite. Abstract 1. Introduction Wepresentanunconditionaldeterministicpolynomialtimealgorithmthat Prime numbers are of fundamental importance in mathematics in general, determines whether an input number is prime or composite. and number theory in particular. So it is of great interest to study different properties of prime numbers. Of special interest are those properties that 1. Introduction allow one to determine efficiently if a number is prime. Such efficient tests are also useful in practice: a number of cryptographic protocols need large prime Prime numbers are of fundamental importance in mathematics in general, 57 numbers. and number theory in particular. So it is of great interest to study different Let PRIMES denote the set of all prime numbers. The definition of prime properties of prime numbers. Of special interest are those properties that numbers already gives a way of determining if a number n is in PRIMES: try allow one to determine efficiently if a number is prime. Such efficient tests are √ dividing n by every number m ≤ n—if any m divides n then it is compos also useful in practice: a number of cryptographic protocols need large prime ite, otherwise it is prime. This test was known since the time of the ancient numbers. Greeks—it is a specialization of the Sieve of Eratosthenes (ca. 240 BC) that Let PRIMES denote the set of all prime numbers. The definition of prime generates all primes less than n. The test, however, is inefficient: it takes numbers already gives a way of determining if a number n is in PRIMES: try √ √ (Ω n) steps to determine if n is prime. An efficient test should need only a dividing n by every number m ≤ n—if any m divides n then it is compos polynomial (in the size of the input = ⌈logn⌉) number of steps. A property ite, otherwise it is prime. This test was known since the time of the ancient that almost gives an efficient test is Fermat’s Little Theorem: for any prime Greeks—it is a specialization of the Sieve of Eratosthenes (ca. 240 BC) that p−1 number p, and any number a not divisible by p, a = 1 (mod p). Given an generates all primes less than n. The test, however, is inefficient: it takes n−1 √ a and n it can be efficiently checked if a = 1 (mod n) by using repeated (Ω n) steps to determine if n is prime. An efficient test should need only a th squaring to compute the (n−1) power of a. However, it is not a correct polynomial (in the size of the input = ⌈logn⌉) number of steps. A property test since many composites n also satisfy it for some a’s (all a’s in case of that almost gives an efficient test is Fermat’s Little Theorem: for any prime Carmichael numbers Car). Nevertheless, Fermat’s Little Theorem became p−1 number p, and any number a not divisible by p, a = 1 (mod p). Given an the basis for many efficient primality tests. n−1 a and n it can be efficiently checked if a = 1 (mod n) by using repeated Since the beginning of complexit th y theory in the 1960s—when the notions squaring to compute the (n−1) power of a. However, it is not a correct of complexity were formalized and various complexity classes were defined— test since many composites n also satisfy it for some a’s (all a’s in case of Carmichael numbers Car). Nevertheless, Fermat’s Little Theorem became The last two authors were partially supported by MHRD grant MHRDCSE20010018. the basis for many efficient primality tests. Since the beginning of complexity theory in the 1960s—when the notions of complexity were formalized and various complexity classes were defined— The last two authors were partially supported by MHRD grant MHRDCSE20010018.Factoring is in NP ∩ coNP FACTORIZE. Given an integer x, find its prime factorization. FACTOR. Given two integers x and y, does x have a nontrivial factor y 
 Theorem. FACTOR ≡ FACTORIZE. P Pf. ≤ trivial. P ≥ binary search to find a factor; divide out the factor and repeat. ▪ P 
 Theorem. FACTOR ∈ NP ∩ coNP. Pf. Certificate: a factor p of x that is less than y. Disqualifier: the prime factorization of x (where each prime factor is less than y), along with a Pratt certificate that each factor is prime. ▪ 58Is factoring in P Fundamental question. Is FACTOR ∈ P 
 Challenge. Factor this number. 74037563479561712828046796097429573142593188889231289 08493623263897276503402826627689199641962511784399589 43305021275853701189680982867331732731089309005525051 16877063299072396380786710086096962537934650563796359 RSA704
 (30,000 prize if you can factor) 59Exploiting intractability Modern cryptography. Ex. Send your credit card to Amazon. Ex. Digitally sign an edocument. Enables freedom of privacy, speech, press, political association. 
 RSA. Based on dichotomy between complexity of two problems. To use: generate two random nbit primes and multiply. To break: suffices to factor a 2nbit integer. RSA sold
 RSA algorithm or design a tshirt for 2.1 billion 60Factoring on a quantum computer 3 Theorem. Shor 1994 Can factor an nbit integer in O(n ) steps
 on a “quantum computer.” 
 
 SIAM REVIEW c 1999 Society for Industrial and Applied Mathematics Vol. 41, No. 2, pp. 303–332 
 PolynomialTimeAlgorithmsfor PrimeFactorizationand 
 DiscreteLogarithmsona ⇤ QuantumComputer 
 † Peter W. Shor 
 Abstract. A digital computer is generally believed to be an e cient universal computing device; that is, it is believed to be able to simulate any physical computing device with an increase in computation time by at most a polynomial factor. This may not be true when quantum 
 mechanics is taken into consideration. This paper considers factoring integers and finding discrete logarithms, two problems that are generally thought to be hard on classical com puters and that have been used as the basis of several proposed cryptosystems. E cient randomized algorithms are given for these two problems on a hypothetical quantum com 
 puter. These algorithms take a number of steps polynomial in the input size, for example, the number of digits of the integer to be factored. Keywords. algorithmic number theory, prime factorization, discrete logarithms, Church’s thesis, 
 quantum computers, foundations of quantum mechanics, spin systems, Fourier trans forms AMSsubjectclassifications. 81P10, 11Y05, 68Q10, 03D10 
 PII.S0036144598347011 2001. Factored 15 = 3 𐄂 5 (with high probability) on a quantum computer. 1. Introduction. One of the first results in the mathematics of computation, which underlies the subsequent development of much of theoretical computer science, 2012. Factored 21 = 3 𐄂 7. was the distinction between computable and noncomputable functions shown in the papers of Church 1936, Post 1936, and Turing 1936. The observation that several apparently di↵ erent definitions of what it meant for a function to be computable 
 yielded the same set of computable functions led to the proposal of Church’s thesis, which says that all computing devices can be simulated by a Turing machine. This thesis greatly simplifies the study of computation, since it reduces the potential field Fundamental question. Does P = BQP of study from any of an infinite number of potential computing devices to Turing machines. Church’s thesis is not a mathematical theorem; to make it one would quantum analog of P require a precise mathematical description of a computing device. Such a description, however, would leave open the possibility of some practical computing device that did 61 (bounded error quantum polynomial time) not satisfy this precise mathematical description and thus would make the resulting theorem weaker than Church’s original thesis. With the development of practical computers, it became apparent that the dis tinctionbetweencomputableandnoncomputablefunctionswasmuchtoocoarse; com ⇤ Published electronically April 23, 1999. This paper originally appeared in SIAM Journal on Computing, Volume 26, Number 5, 1997, pages 1484 to 1509. http://www.siam.org/journals/sirev/412/34701.html † ATT Labs–Research, Room C237, 180 Park Avenue, Florham Park, NJ 07932 (shor research.att.com). 3038. INTRACTABILITY II P vs. NP ‣ NPcomplete ‣ coNP ‣ NPhard ‣A note on terminology 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Note. The term x does not necessarily imply that a problem is in NP,
 just that every problem in NP polytime reduces to x. 63A note on terminology Knuth's original suggestions. Hard. so common that it is unclear whether it is being used in a technical sense Tough. Herculean. Formidable. Arduous. assign a real number between 0 and 1 to each choice 64A note on terminology Some English word writeins. Impractical. Bad. Heavy. Tricky. Intricate. Prodigious. Difficult. Intractable. Costly. Obdurate. Obstinate. Exorbitant. Interminable. 65A note on terminology Hardboiled. Ken Steiglitz In honor of Cook. 
 Hardass. Al Meyer Hard as satisfiability. 
 Sisyphean. Bob Floyd Problem of Sisyphus was timeconsuming. 
 Ulyssean. Donald Knuth Ulysses was known for his persistence. “ creative research workers are as full of ideas for new terminology as they are empty of enthusiasm for adopting it. ” — Donald Knuth 66A note on terminology: acronyms PET. Shen Lin Probably exponential time. If P ≠ NP, provably exponential time. If P = NP, previously exponential time. 
 GNP. Al Meyer Greater than or equal to NP in difficulty. And costing more than the GNP to solve. 67A note on terminology: madeup words Exparent. Mike Paterson Exponential + apparent. 
 Perarduous. Mike Paterson Throughout (in space or time) + completely. 
 Supersat. Al Meyer Greater than or equal to satisfiability. 
 Polychronious. Ed Reingold Enduringly long; chronic. 68A note on terminology: consensus NPcomplete. A problem in NP such that every problem in NP polytime reduces to it. 
 NPhard. Bell Labs, Steve Cook, Ron Rivest, Sartaj Sahni
 A problem such that every problem in NP polynomialtime reduces to it. 69
Website URL
Comment