8. INTRACTABILITY II
‣ P vs. NP
‣ NP-complete ‣ co-NP
‣ NP-hard
Lecture slides by Kevin Wayne
Copyright © 2005 Pearson-Addison Wesley
http://www.cs.princeton.edu/~wayne/kleinberg-tardos
Last updated on 2/16/20 10:57 AM
Recap
3-SAT
INDEPENDENT-SET
DIR-HAM-CYCLE
3-COLOR
SUBSET-SUM
VERTEX-COVER
HAM-CYCLE
KNAPSACK
3-SAT poly-time reduces to all of these problems (and many, many more)
SET-COVER
2
3-SAT poly-time reduces to INDEPENDENT-SET
8. INTRACTABILITY II
‣ P vs. NP
‣ NP-complete ‣ co-NP
‣ NP-hard
SECTION 8.3
P
Decision problem.
・Problem X is a set of strings. ・Instance s is one string.
・Algorithm A solves problem X : A(s) =
s X s / X
Def. Algorithm A runs in polynomial time if for every string s, A(s) terminates in ≤ p( ⎢s ⎢) “steps,” where p(⋅) is some polynomial function.
length of s
Def. P = set of decision problems for which there exists a poly-time algorithm.
on a deterministic Turing machine
problem PRIMES: instance s: algorithm:
{ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, … } 592335744548702854681 Agrawal–Kayal–Saxena (2002)
4
Some problems in P
P. Decision problems for which there exists a poly-time algorithm.
problem
description
poly-time algorithm
yes
no
MULTIPLE
Is x a multiple of y ?
grade-school division
51, 17
51, 16
REL-PRIME
Are x and y relatively prime ?
Euclid’s algorithm
34, 39
34, 51
PRIMES
Is x prime ?
Agrawal–Kayal– Saxena
53
51
EDIT-DISTANCE
Is the edit distance between x and y less than 5 ?
Needleman–Wunsch
niether
neither
acgggt
ttttta
L-SOLVE
Is there a vector x that satisfies Ax = b ?
Gauss–Edmonds elimination
#0 1 1& #4& %2 4 −2(,%2(
%0 3 15( %36( $ ‘$’
“1 0 0% “1% $1 1 1′ , $1′
$0 1 1′ $1′ #&#&
U-CONN
Is an undirected graph G connected?
depth-first search€
€
5
NP
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.
Def. NP = set of decision problems for which there exists a poly-time certifier. ・C(s, t) is a poly-time algorithm.
・Certificate t is of polynomial size: ⎢t ⎢ ≤ p(⎢s ⎢) for some polynomial p(⋅).
“certificate” or “witness”
problem COMPOSITES: instance s:
certificate t:
certifier C(s, t):
{ 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, …. } 437669
541
437,669 = 541 × 809
grade-school division
6
Certifiers and certificates: satisfiability
SAT. Given a CNF formula Φ, does it have a satisfying truth assignment? 3-SAT. 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.
instances Φ =(x1 ∨x2 ∨x3)∧(x1 ∨x2 ∨x3)∧(x1 ∨x2 ∨x4) certificate t x1 = true, x2 = true, x3 = false, x4 = false
€
Conclusions. SAT ∈ NP, 3-SAT ∈ NP.
7
Certifiers and certificates: Hamilton path
HAMILTON-PATH. 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 π contains each node in V exactly once,
and that G contains an edge between each pair of adjacent nodes.
instance s certificate t
Conclusion. HAMILTON-PATH ∈ NP.
8
Some problems in NP
NP. Decision problems for which there exists a poly-time certifier.
problem
description
poly-time algorithm
yes
no
L-SOLVE
Is there a vector x that satisfies Ax = b ?
Gauss–Edmonds elimination
#0 1 1& #4& %2 4 −2(,%2(
%0 3 15( %36( $ ‘$’
“1 0 0% “1% $1 1 1′ , $1′
$0 1 1′ $1′ #&#&
COMPOSITES
Is x composite ?
Agrawal–Kayal– Saxena
€
€
51
53
FACTOR
Does x have a nontrivial factor less than y ?
(56159, 50)
(55687, 50)
SAT
Given a CNF formula, does it have a satisfying truth assignment?
¬x1 ∨¬x2 ∨¬x3 ¬x1 ∨¬x2 ∨¬x3 ¬x1 ∨¬x2 ∨¬x3
¬x1 ∨¬x2 ¬x1 ∨¬x2 ¬x1 ∨¬x2
HAMILTON- PATH
Is there a simple path between u and v that visits every node?
9
Intractability: quiz 1
Which of the following graph problems are known to be in NP?
A. Is the length of the longest simple path ≤ k ?
B. Is the length of the longest simple path ≥ k ?
C. Is the length of the longest simple path = k ?
D. Find the length of the longest simple path.
E. All of the above.
10
Intractability: quiz 2
In complexity theory, the abbreviation NP stands for…
A. Nope.
B. No problem.
C. Not polynomial time.
D. Not polynomial space.
E. Nondeterministic polynomial time.
11
Significance of NP
NP. Decision problems for which there exists a poly-time 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
12
P, NP, and EXP
P. Decision problems for which there exists a poly-time algorithm.
NP. Decision problems for which there exists a poly-time certifier.
EXP. Decision problems for which there exists an exponential-time algorithm.
Proposition. P ⊆ NP.
Pf. Consider any problem X ∈ P.
・By definition, there exists a poly-time algorithm A(s) that solves X. ・Certificate t = ε, certifier C(s, t) = A(s). ▪
Proposition. NP ⊆ EXP.
Pf. Consider any problem X ∈ NP.
・By definition, there exists a poly-time certifier C(s, t) for X, where certificate t satisfies ⎢t⎢ ≤ p(⎢s⎢) for some polynomial p(⋅).
・To solve instance s, run C(s, t) on all strings t with ⎢t⎢ ≤ p(⎢s⎢). ・Return yes iff C(s, t) returns yes for any of these potential certificates. ▪
Fact. P ≠ EXP ⇒ either P ≠ NP, or NP ≠ EXP, or both.
13
The main question: P vs. NP
Q. How to solve an instance of 3-SAT with n variables? A. Exhaustive search: try all 2n truth assignments.
Q. Can we do anything substantially more clever? Conjecture. No poly-time algorithm for 3-SAT.
“intractable”
14
The 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?
EXP EXP
P = NP
If P=NP
NP P
If P≠NP
If yes… Efficient algorithms for 3-SAT, TSP, VERTEX-COVER, FACTOR, …
If no… No efficient algorithms possible for 3-SAT, TSP, VERTEX-COVER, …
Consensus opinion. Probably no.
15
Reductions: quiz 3
Suppose P ≠ NP. Which of the following are still possible?
A. O(n3) algorithm for factoring n-bit integers.
B. O(1.657n) time algorithm for HAMILTON-CYCLE.
C. O(nlog log log n) algorithm for 3-SAT.
D. All of the above.
16
Intractability: quiz 4
Does P = NP?
A. Yes.
B. No.
C. None of the above.
17
Possible 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
“ 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 half-life of this problem at 25–50
more years, but I wouldn’t bet on it being solved before 2100. ”
— Bob Tarjan (2002)
18
Possible outcomes
P ≠ NP
“ 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)
19
Possible 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)
“ In my opinion this shouldn’t really be a hard problem; it’s just
that we came late to this theory, and haven’t yet developed any techniques for proving computations to be hard. Eventually, it will just be a footnote in the books. ” — John Conway
20
Other possible outcomes
P = NP, but only Ω(n100) algorithm for 3-SAT.
P ≠ NP, but with O(nlog*n) algorithm for 3-SAT.
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
21
Millennium prize
Millennium prize. $1 million for resolution of P ≠ NP problem.
22
P vs. NP and pop culture
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
23
Princeton CS Building, West Wall, Circa 2001
24
Princeton CS Building, West Wall, Circa 2001
101 0110000
100110 1011111
0110000
1110 1
char
ASCII
binary
P
80
1010000
=
61
0111101
N
78
1001110
P
80
1010000
?
63
0111111
25
8. INTRACTABILITY II
‣ P vs. NP
‣ NP-complete ‣ co-NP
‣ NP-hard
SECTION 8.4
Polynomial transformations
Def. Problem X polynomial (Cook) reduces to problem Y if arbitrary in・stances 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 instance x of X, we can construct an instance y of 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 ≤ P and blur distinction
27
NP-complete
NP-complete. A problem Y ∈ NP with the property that for every problemX∈NP,X≤P Y.
Proposition. Suppose Y ∈ NP-complete. 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 ≤ P Y, we have X ∈ P. ・This implies NP ⊆ P.
・We already know P ⊆ NP. Thus P = NP. ▪
Fundamental question. Are there any “natural” NP-complete problems?
28
The “first” NP-complete problem
Theorem. [Cook 1971, Levin 1973] SAT ∈ NP-complete.
Summary
It problem bounded machine blem of
is shown that any recognition solved by a polynomial time- nondeterministic Turing
can be “reduced” to the pro- determining whether a given
certain recursive set of strings on this alphabet, and we are interested in the problem of finding a good lower bound on its possible recog- nition times. We provide no such lower bound here, but theorem 1 will give evidence that {tautologies} is a difficult set to recognize, since many apparently difficult problems can be reduced to determining tau- tologyhood. By reduced we mean, roughly speaking, that if tauto- logyhood could be decided instantly
519.14
propositional formula is a tautology. Here “reduced” means, roughly speak- ing, that the first problem can be solved deterministically in polyno- mial time provided an oracle is available for solving the second. From this notion of reducible, polynomial degrees of difficulty are defined, and it is shown that the problem of determining tautologyhood has the same polynomial degree as the problem of determining whether the first of two given graphs is iso- morphic to a subgraph of the second. Other examples are discussed. A method of measuring the complexity of proof procedures for the predicate calculus is introduced and discussed.
Throughout this paper, a set of strings means a set of strings on some fixed, large, finite alphabet Z. This alphabet is large enough to in- clude symbols for all sets described here. All Turing machines are deter- ministic recognition devices, unless the contrary is explicitly stated.
i. Tautologies and Polynomial Re- Reducibility.
Let us fix a formalism for the propositional calculus in which formulas are written as strings on I. Since we will re- quire infinitely many proposition symbols (atoms), each such symbol will consist of a member of Z followed by a number in binary notation to distinguish that symbol. Thus a formula of length n can only have about n/logn distinct function and predicate symbols. The logical connectives are & (and), v (or), and ~(not).
The set of tautologies (denoted by {tautologies}) is a
» .
«»,
The Complexity of Theorem-Proving Procedures Stephen A. Cook
University of Toronto
IX 1973 .3
-151-
29
(by an “oracle”) then these problems , could be decided in polynomial time. ).
,
(
– , –
–
In order to make this notion precise, we introduce query machines, which are like Turing machines with oracles
in [I].
A query machine is a multitape Turing machine with a distinguished tape called the query tape, and three distinguished states called the query state, yes state, and n._o_ state, respectively. If M is a query machine and T is a set of strings, then a T-computation of M
is a computation of M in which initially M is in the initial state and has an input string w on its input tape, and each time M assumes the query state there is a string u on the query tape, and the next state M assumes is the yesstateif uET andthenostate ifu~T.Wethinkofan”oracle”, which knows T, placing M in the yes state or no state.
Definition
A set S of strings is P-redu-
.
-,- .- :,,
. ,.-
cible (P for polynomial) to a set . T of strings iff there is some
query machine M and a polynomial 2. Q(n) such that for each input string
).
. ,.
500- (
.
w, the T-computation of M with in- put w halts within Q(Iwl) steps
(lwl is the length of w~ and ends in an accepting state iff wcS.
It is not hard to see that P-reducibility is a transitive re- lation. Thus the relation E on
3., – .(,, .) 4.. (
).
5.. ().
6. 1 100 – ,- .-
. (
,
,
,
.)
–
– ( –
,- .
f{n) g{n)
f(n) ^ (g(n)+2)*
,
–
,
(
1,2]),
, .-
, ),
(),,- «»(- , .). –
.
,
1.
,
,,—
, ;,-).-
,. .-
.
«
«
(
». (, )—
)
g(n) < (f(n) +2)*.
(, )», ,.(-
,
( ).
-
.
-
,
Establishing NP-completeness
Remark. Once we establish first “natural” NP-complete problem, others fall like dominoes.
Recipe. To prove that Y ∈ NP-complete: ・Step 1. Show that Y ∈ NP.
・Step 2. Choose an NP-complete problem X.
・Step 3. Prove that X ≤
Proposition. If X ∈ NP-complete, Y ∈ NP, and X ≤ P Y, then Y ∈ NP-complete. P・f. Consider any problem W ∈ NP. Then, both W ≤P X and X ≤P Y.
P
Y.
・By transitivity, W ≤ Y. P
Hence Y ∈ NP-complete. ▪
by definition of by assumption NP-complete
30
Reductions: quiz 4
Suppose that X ∈ NP-COMPLETE, Y ∈ NP, and X ≤ P Y. Which can you infer?
A. Y is NP-complete.
B. If Y ∉ P, then P ≠ NP.
C. If P ≠ NP, then neither X nor Y is in P.
D. All of the above.
recipe for proving that Y is NP-complete Y is NP-complete
X and Y are NP-complete
31
Implications of Karp
SAT
3-SAT
INDEPENDENT-SET
VERTEX-COVER
SET-COVER
DIR-HAM-CYCLE
HAM-CYCLE
3-COLOR
SUBSET-SUM
KNAPSACK
SAT poly-time reduces to all of these problems (and many, many more)
32
3-SAT poly-time reduces to INDEPENDENT-SET
Implications of Cook–Levin
SAT
3-SAT
INDEPENDENT-SET
VERTEX-COVER
SET-COVER
DIR-HAM-CYCLE
HAM-CYCLE
3-COLOR
SUBSET-SUM
KNAPSACK
All of these problems (and many, many more) poly-time reduce to SAT.
33
INDEPENDENT-SET poly-time reduces to CIRCUIT-SAT
Implications of Karp + Cook–Levin
SAT
3-SAT
INDEPENDENT-SET
VERTEX-COVER
SET-COVER
DIR-HAM-CYCLE
HAM-CYCLE
3-COLOR
SUBSET-SUM
KNAPSACK
All of these problems are NP-complete; they are manifestations of the same really hard problem.
34
3-SAT and INDEPENDENT-SET poly-time reduce to one another
I’D TELL YOU ANOTHER NP-COMPLETE JOKE, BUT ONCE YOU’VE HEARD ONE,
YOU’VE HEARD THEM ALL.
35
Some NP-complete problems
B・asic genres of NP-complete problems and paradigmatic examples. ・Packing/covering problems: SET-COVER, VERTEX-COVER,INDEPENDENT-SET. ・Constraint satisfaction problems: CIRCUIT-SAT, SAT, 3-SAT. ・Sequencing problems: HAMILTON-CYCLE, TSP.
・Partitioning problems: 3D-MATCHING, 3-COLOR. Numerical problems: SUBSET-SUM, KNAPSACK.
Practice. Most NP problems are known to be either in P or NP-complete. NP-intermediate? FACTOR, DISCRETE-LOG, GRAPH-ISOMORPHISM, ....
Theorem. [Ladner 1975] Unless P = NP, there exist problems in NP that are neither in P nor NP-complete.
On the Structure of Polynomial Time Reducibility
RICHARD E. LADNER
Umvers~ty of Wash~r~g~on,Seattle, Washington
ABSTRACT Two notions of polynomml time reduclbihty, denoted here by ~ Te and <.~P, were de- fined by Cook and Karp, respectively The abstract propertms of these two relatmns on the domain of computable sets are investigated. Both relations prove to be dense and to have minimal pairs. Further, there is a strictly ascending sequence with a minimal pair of upper bounds to the sequence. Our method of showing density ymlds the result that if P ~ NP then there are members of NP -- P
36
More hard computational problems
Garey and Johnson. Computers and Intractability. ・Appendix includes over 300 NP-complete problems. ・Most cited reference in computer science literature.
37
More 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 a1, ..., an, compute
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, Rubik’s Cube. Statistics. Optimal experimental design.
38
Extent and impact of NP-completeness
Extent of NP-completeness. [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.
NP-completeness can guide scientific inquiry.
・1926: Ising introduces simple model for phase transitions.
・1944: Onsager finds closed-form solution to 2D-ISING in tour de force.
・19xx: Feynman and other top minds seek solution to 3D-ISING.
・2000: Istrail proves 3D-ISING ∈ NP-complete. a holy grail of statistical mechanics
search for closed formula appears doomed
39
You NP-complete me
40
8. INTRACTABILITY II
‣ P vs. NP
‣ NP-complete ‣ co-NP
‣ NP-hard
SECTION 8.9
Asymmetry of NP
Asymmetry of NP. We need short certificates only for yes instances.
Ex 1. SAT vs. UN-SAT.
・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? UN-SAT. Given a CNF formula Φ, is there no satisfying truth assignment?
42
Asymmetry of NP
Asymmetry of NP. We need short certificates only for yes instances.
Ex 2. HAMILTON-CYCLE vs. NO-HAMILTON-CYCLE.
・Can prove a graph is Hamiltonian by specifying a permutation. ・How could we prove that a graph is not Hamiltonian?
HAMILTON-CYCLE. Given a graph G = (V, E), is there a simple cycle Γ that contains every node in V ?
NO-HAMILTON-CYCLE. Given a graph G = (V, E), is there no simple cycle Γ that contains every node in V ?
43
Asymmetry of NP
Asymmetry of NP. We need short certificates only for yes instances.
Q. How to classify UN-SAT and NO-HAMILTON-CYCLE ?
・SAT ∈ NP-complete and SAT ≡ P UN-SAT.
・HAMILTON-CYCLE ∈ NP-complete and HAMILTON-CYCLE ≡ P NO-HAMILTON-CYCLE. ・But neither UN-SAT nor NO-HAMILTON-CYCLE are known to be in NP.
44
NP and co-NP
NP. Decision problems for which there is a poly-time certifier. Ex. SAT, HAMILTON-CYCLE, 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, ... }
X = { 2, 3, 5, 7, 11, 13, 17, 23, 29, ... }
ignore 0 and 1 (neither prime nor composite)
co-NP. Complements of decision problems in NP. Ex. UN-SAT, NO-HAMILTON-CYCLE, and PRIMES.
45
NP = co-NP ?
Fundamental open question. Does NP = co-NP?
・Do yes instances have succinct certificates iff no instances do? ・Consensus opinion: no.
Theorem. If NP ≠ co-NP, then P ≠ NP. Pf idea.
・P is closed under complementation.
・If P = NP, then NP is closed under complementation. ・In other words, NP = co-NP.
・This is the contrapositive of the theorem.
46
Good characterizations
G・ood characterization. [Edmonds 1965] NP ∩ co-NP. If problem X is in both NP and co-NP, then:
- -
Provides conceptual leverage for reasoning about a problem.
E・x. 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 Standards-B. Mathematics and Mathematical Physics
Vol. 69B, Nos. 1 and 2, January-June 1965
Minimum Partition of a Matroid Into Independent Subsets!
Jack Edmonds (December 1, 1964)
A matroid M is a finite set M of elements with a family of subsets, called independent, such that (I) every subset of an independent set is independent, and (2) for every subset A of M, all maximal independent subsets of A have the same cardinality, called the rank r\A) of A. It is proved that a matroid can be partitioned into as few as k sets, each independent, if and only if every subset A has cardinality at mos t k . r(A ).
for yes instance, there is a succinct certificate ・ for no instance, there is a succinct disqualifier
1.0. Introduction
Matroids can be regarded as a certain abstraction the nodes of the graph. An edge and a node are said
which has exactly two ones in each column. The 47
columns are the edges of the graph and the rows are
ubtedly set- h
e h
n
2
b
n n
o n
i s
entail a horrendous amount of work.
We seek an al-
, rCA), of the
all matroids via the matroid axioms. However, the
the packing ted packing
gorithm for which the work involved increases only algebraically with the size of the matrix to which it is
Good characterizations
e by the ex-
blem is in a system of
graph, and independent
e following:
ts, all maxi- ain the same
nts and sets .
system con- d all of the dependence ence system to be trivial For me, hav- blems, it is ids have a
the special
s a matroid. ame symbol e rank, rCA),
applied, where we regard the size of a matrix as in- creasing only linearly with the number of columns, the number of rows, and the characteristic of the field. As in most combinatorial problems, finding a finite algorithm is trivial but finding an algorithm which meets this condition for practical feasibility is not trivial.
We seek a good characterization of the minimum number of independent sets into which the columns of a matrix of Mr can be partitioned. As the criterion
of "good" for the characterization we apply the "prin- ciple of the absolute supervisor." The good charac- terization will describe certain information about the matrix which the supervisor can require his assistant to search out along with a minimum partition and which the supervisor can then use with ease to verify with mathematical certainty that the partition is in- deed minimum. Having a good characterization does not mean necessarily that there is a good algorithm. The assistant might have to kill himself with work to find the information and the partition.
Theorem 1 on partitioning matroids provides the good characterization in the case of matrices of Mr. The proof of the theorem yields a good algorithm in the case of matrices of Mr. (We will not elaborate on how.) The theorem and the proof apply as well to
48
Good characterizations
Observation. P ⊆ NP ∩ co-NP.
・Proof of max-flow min-cut theorem led to stronger result that max-flow
and min-cut are in P.
・Sometimes finding a good characterization seems easier than finding an
efficient algorithm.
Fundamental open question. Does P = NP ∩ co-NP?
・Mixed opinions.
・Many examples where problem found to have a nontrivial good
characterization, but only years later discovered to be in P.
49
Linear programming is in NP ∩ co-NP
LINEAR-PROGRAMMING. Given A ∈ Rm×n, b ∈ Rm, c ∈ Rn, and α ∈ R, does there
exist x ∈ Rn such that Ax ≤ b, x ≥ 0 and cT x ≥ α ?
Theorem. [Gale–Kuhn–Tucker 1948] LINEAR-PROGRAMMING ∈ NP ∩ co-NP.
Pf sketch. If (P) and (D) are nonempty, then max = min.
(P) maxcT x (D) minyTb
s. t. Ax ≤ b s. t. AT y ≥ c
x≥0 y≥0
€€
50
Linear programming is in NP ∩ co-NP
LINEAR-PROGRAMMING. Given A ∈ Rm×n, b ∈ Rm, c ∈ Rn, and α ∈ R, does there
exist x ∈ Rn such that Ax ≤ b, x ≥ 0 and cT x ≥ α ? Theorem. [Khachiyan 1979] LINEAR-PROGRAMMING ∈ P.
20 1980 ,1
(0.1)
(0.2)
(1 1- ;..+ {
< {,
m>2 ^2 .. ., x h …, :
i=l, 2,…, ,
Yilog2 (1bi 1+1} + log2
L = [2J uii
LOG2(1 1+1)+
+ 1
aih b{.
, . .
0 1,
.. ()
519.852
,- .
51
.
Primality testing is in NP ∩ co-NP
Theorem. [Pratt 1975] PRIMES ∈ NP ∩ co-NP.
SIAM J. COMPUT.
Vol. 4, No. 3, September 1975
EVERY PRIME HAS A SUCCINCT CERTIFICATE* VAUGHAN R. PRATTf
Abstract. To prove that a number n is composite, it suffices to exhibit the working for the multiplica- tion of a pair of factors. This working, represented as a, string, is of length bounded by a polynomial inlog n.Weshowthatthesamepropertyholdsfortheprimes.Itisnoteworthythatalmostnoother set is known to have the property thatshort proofs for membership or nonmembership exist for all candidates without being known to have the property that such proofs are easy to come by. It remains an open problem whether a prime n can be recognized in only log n operations of a Turing machine for any fixed
The proof system used for certifying primes is as follows. AXIOM. (x,y, 1).
INFERENCE RULES.
(p, x, a), q -(p, x, qa) provided xtp- 1)/q (mod p) and ql(P 1).
p- ,_
)p providedx (modp).
THEOREM1.pisatheorem pisaprime. THEOREM2.pisatheorem phasaproofof[4log p lines.
Key words, primes, membership, nondeterministic, proof, NP-complete, computational complexity
1. Proofs. We know of no efficient method that will reliably tell whether
a given number is prime or composite. By “efficient”, we mean a method for which
the time is at most a polynomial in the length of the number written in positional 52 notation. Thus the cost of testing primes and composites is very high. In contrast,
R1 R2:
(p,x,p- 1
Primality testing is in NP ∩ co-NP
Theorem. [Pratt 1975] PRIMES ∈ NP ∩ co-NP.
Pf sketch. An odd integer s is prime iff there exists an integer 1 < t < s s.t.
ts−1 ≡ 1 (mods) t(s−1)/p ≠ 1 (mods)
for all prime divisors p of s-1
CERTIFIER (s) __________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
CHECK s – 1 = 2 × 2 × 3 × 36473. CHECK 17s–1 = 1 (mod s).
CHECK 17(s–1) / 2 ≡ 437676 (mod s). CHECK 17(s–1) / 3 ≡ 329415 (mod s).
CHECK 17(s–1) / 36,473 ≡ 305452 (mod s). __________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
€
instance s 437677
certificate t 17, 22 × 3 × 36473
prime factorization of s–1
also need a recursive certificate
to assert that 3 and 36,473 are prime
use repeated squaring
53
Primality testing is in P
Theorem. [Agrawal–Kayal–Saxena 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*
We present an unconditional deterministic polynomial-time algorithm that
determines whether an input number is prime or composite.
Abstract
1. Introduction
We present an unconditional deterministic polynomial-time algorithm that
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,
numbers.
and number theory in particular. So it is of great interest to study different
54
Let PRIMES denote the set of all prime numbers. The definition of prime properties of prime numbers. Of special interest are those properties that
Factoring is in NP ∩ co-NP
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 ≡ P FACTORIZE. Pf.
・≤ P trivial.
・≥ P binary search to find a factor; divide out the factor and repeat. ▪
Theorem. FACTOR ∈ NP ∩ co-NP. P・f.
・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. ▪
55
Is factoring in P ?
Fundamental question. Is FACTOR ∈ P ? Challenge. Factor this number.
74037563479561712828046796097429573142593188889231289
08493623263897276503402826627689199641962511784399589
43305021275853701189680982867331732731089309005525051
16877063299072396380786710086096962537934650563796359
RSA-704
($30,000 prize if you can factor)
56
Exploiting intractability
Modern cryptography.
・Ex. Send your credit card number to Amazon.
・Ex. Digitally sign an e-document.
・Enables freedom of privacy, speech, press, political association.
RSA. Based on dichotomy between complexity of two problems. ・To use: generate two random n-bit primes and multiply. ・To break: suffices to factor a 2n-bit integer.
RSA algorithm
RSA sold
for $2.1 billion
or design a t-shirt
57
Factoring on a quantum computer
Theorem. [Shor 1994] Can factor an n-bit integer in O(n3) steps on a “quantum computer.”
SIAM REVIEW ∞c 1999 Society for Industrial and Applied Mathematics Vol. 41, No. 2, pp. 303–332
Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer§
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.
Key words. algorithmic number theory, prime factorization, discrete logarithms, Church’s thesis,
quantum computers, foundations of quantum mechanics, spin systems, Fourier trans- forms
AMS subject classifications. 81P10, 11Y05, 68Q10, 03D10
PII. S0036144598347011
2001. Factored 15 = 3 𐄂 5 (with high probability) on a quantum computer.
2012. Factored 21 = 3 𐄂 7.
was the distinction between computable and noncomputable functions shown in the
1. Introduction. One of the first results in the mathematics of computation, which underlies the subsequent development of much of theoretical computer science,
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
Fundamental question. Does P = BQP ?
of study from any of an infinite number of potential computing devices to Turing
thesis greatly simplifies the study of computation, since it reduces the potential field
machines. Church’s thesis is not a mathematical theorem; to make it one would require a precise mathematical description of a computing device. Such a description,
quantum analog of P
however, would leave open the possibility of some practical computing device that did 58
not satisfy this precise mathematical description and thus would make the resulting
theorem weaker than Church’s original thesis.
(bounded error quantum polynomial time)
With the development of practical computers, it became apparent that the dis-
8. INTRACTABILITY II
‣ P vs. NP
‣ NP-complete ‣ co-NP
‣ NP-hard
A note on terminology
Note. The term x does not necessarily imply that a problem is in NP, just that every problem in NP poly-time reduces to x.
60
A note on terminology
Knuth’s original suggestions.
・Hard. ・Tough. ・Herculean. ・Formidable. ・Arduous.
so common that it is unclear whether it is being used in a technical sense
assign a real number between 0 and 1 to each choice
61
A note on terminology
Some English word write-ins.
・Impractical. ・Bad. ・Heavy. ・Tricky. ・Intricate. ・Prodigious. ・Difficult. ・Intractable. ・Costly. ・Obdurate. ・Obstinate. ・Exorbitant. ・Interminable.
62
A note on terminology
Hard-boiled. [Ken Steiglitz] In honor of Cook.
Hard-ass. [Al Meyer] Hard as satisfiability.
Sisyphean. [Bob Floyd] Problem of Sisyphus was time-consuming. 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
63
A 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.
64
A note on terminology: made-up 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.
65
A note on terminology: consensus
NP-complete. A problem in NP such that every problem in NP poly-time reduces to it.
NP-hard. [Bell Labs, Steve Cook, Ron Rivest, Sartaj Sahni]
A problem such that every problem in NP poly-time reduces to it.
66