CS

580
ALGORITHM DESIGN AND ANALYSIS

NP and NP-completeness
Vassilis Zikas
 SO FAR

• Defined Cook reductions

• Saw some simple reduction strategies
• 3-SAT≤! INDEPENDENT SET ≤! VERTEX
COVER ≤! SET COVER

• Today:
◦ The class NP! (8.3 in KT)
◦ NP-completeness
◦ co-NP
 MORE REDUCTION STRATEGIES

• Decision problem:
◦ Does there exist a vertex cover of size ≤ F?
• Search problem:
◦ Find the vertex cover of minimum cardinality
• Self-reducibility:
◦ Search version ≤) decision version
◦ Applies to all NP-complete problems
◦ Justifies our focus on decision problems
 MORE REDUCTION STRATEGIES

• Self-reducibility for vertex cover

◦ Binary search for cardinality F ∗ of min vertex
cover
◦ Find a vertex O such that P − O has a vertex
cover of size F ∗ − 1
• Any vertex in any min vertex cover will have this
property
◦ Include O in the vertex cover
◦ Recursively find a min vertex cover in P − {O}
8.3: DEFINITION OF NP
 DECISION PROBLEMS
• Decision problem
◦ ! is a set of strings
◦ Instance: string 0
◦ Algorithm 5 solves problem !:
• ! " = $%" if and only if " ∈ 0

• Algorithm 2 runs in polynomial time if for

every string 8, 2(8) terminates in at most
<( 8 ) steps, where <(. ) some polynomial

• PRIMES: {2, 3, 5, 7, 11, 13, 17, 23, 29, 31, … }

◦ Algorithm: [Agrawal et al. 2002] ? 0 = 0!
 DEFINITION OF P

• P: Decision problems for which there is a

poly-time algorithm.
Problem Description Algorithm Yes No

Grade school
MULTIPLE Is x a multiple of y? 51, 17 51, 16
division

RELPRIME Are x and y relatively prime? Euclid (300 BCE) 34, 39 34, 51

PRIMES Is x prime? AKS (2002) 53 51

EDIT- Is the edit distance between Dynamic niether acgggt

DISTANCE x and y less than 5? programming neither ttttta

é 0 1 1ù é 4 ù é 1 0 0 ù é1ù
Is there a vector x that Gauss-Edmonds
LSOLVE ê ú ê ú
ê 2 4 -2 ú , ê 2 ú
ê ú ê ú
ê 1 1 1ú , ê1ú
satisfies Ax = b? elimination êë 0 3 15 úû êë36 úû êë0 1 1úû êë1ûú
 CERTIFICATES
• Finding a solution versus checking a solution
• We do not know good algorithms that decide
whether a CNF formula is satisfiable
• But, given a proposed solution we can quickly
check if it satisfies the formula or not
• Given a CNF formula one can provide evidence
that the formula is satisfiable
◦ Evidence = satisfying assignment
• What evidence is there that a formula is not
satisfiable?
• Formalizing “evidence” is going to be crucial
for us
 CERTIFIER

• An algorithm K(M, O) is an efficient certifier

for a problem Q if
◦ W runs in polynomial time
◦ For every string X, we have X ∈ \ if and only if
there exists a string ] such that W X, ] = _`X
• O is called the “certificate” or “witness”
 NP

NP (nondeterministic polynomial time) is the

set of all problems for which there exists an
efficient certifier
 CERTIFIERS AND CERTIFICATES: 3-
SAT
• SAT:
◦ Given a CNF formula 7 is there a satisfying assignment?
• Certificate:
◦ An assignment of truth values to the > Boolean variables
• Certifier:
◦ Check that each clause in 7 has at least one true literal

• Example:

( x1 Ú x2 Ú x3 ) Ù ( x1 Ú x2 Ú x3 ) Ù ( x1 Ú x2 Ú x4 ) Ù (x1 Ú x3 Ú x4 )

Certificate *: x1 = 1, x2 = 1, x3 = 0, x4 = 1

• Conclusion: SAT is in NP
 CERTIFIERS AND CERTIFICATES:
HAMILTON CYCLE
• HAM-CYCLE: Given an undirected graph K, does there exist a
simple cycle M that visits every node?
• Certificate: Ordered list of nodes
• Certifier: Check that the ordered list contains each node in Q
exactly once, and that there is an edge between adjacent nodes
in the list (and between the first and last node).
• Conclusion: HAM-CYCLE in NP

instance s certificate t
 P, NP, EXP
• P: Decision problems for which there is poly-time algorithm
• NP: Decision problems for which there is a poly-time certifier
• EXP: Decision problems for which there is an exponential time
algorithm

• Claim: Z ⊆ \Z
◦ Proof: Consider any problem F in P
◦ By definition, there exists a poly-time algorithm J(L) that solves F
◦ Certificate N = ∅, certifier Q L, N = J(L)

• Claim: \Z ⊆ ]0Z
◦ Proof: Consider any problem F in NP
◦ By definition, there exists a poly-time certifier Q(L, N) for F
◦ To solve input L, run Q(L, N) on all strings N with N ≤ U( L )
◦ Return WXL if Q(L, N) returns WXL for any of these
 THE QUESTION

• Does P=NP? [Cook 1971, Edmonds, Levin,

Yablonksi, Godel]
• Is a solving a problem easier than verifying
a solution?
◦ Easiest way to become the most famous
computer scientist alive!
◦ Clay prize: 1 million dollars
 P VERSUS NP

EXP NP EXP
P P = NP

If P ¹ NP If P = NP
 P VERSUS NP

• If ^ = _^ the economy will probably

collapse
◦ E.g. RSA is no longer secure, and therefore our
bank accounts are no longer secure
• If ^ ≠ _^, no efficient algorithms for 3-SAT,
INDEPENDENT SET, SET COVER,…

• Consensus: most people believe that ^ ≠

_^
 NP-COMPLETENESS (8.4 IN KT)

• Cook reduction: Problem Q polynomial

reduces to problem b if arbitrary instances
of Q can be solved using:
◦ Polynomial number of standard steps, and
◦ Polynomial number of queries to an oracle for f
• Karp reduction: Problem X polynomial
reduces to problem b if given any input d of
Q we can construct an input e of b, such that
d is a efM instance of Q if and only if e is a
efM instance of b
 NP-COMPLETENESS
• Most reductions we’ve seen so far are actually
Karp reductions
◦ Only one call at the oracle for E, at the end
• Cook and Karp reductions are not known to be
the same with respect to NP
◦ In a Cook reduction, we call the oracle multiple
times, perhaps adaptively
• If they are the same, then ^_-NP = NP
• If they are not the same then b ≠ db
• We will mostly focus on Karp reductions, since
they are the standard type
 NP-COMPLETENESS
• Definition: A problem 0 is NP-hard, if for every ; in
NP, ; ≤) 0
• Definition: A problem 0 in NP is NP-complete, if for
every ; in NP, ; ≤) 0
• Theorem: Suppose 0 is an NP-complete problem.
Then 0 is solvable in polynomial time if and only if
P=NP
• Proof:
◦ ⟸ If P=NP H can be solved in polytime since it’s in LM
◦ ⟹ Suppose H is solvable in polynomial time. Let R be an
arbitrary problem in LM. Since R ≤, H we can solve R in
polytime, thus LM ⊆ M. We already know that M ⊆ LM
• Fundamental question: Are there “natural” NP-
complete problems?
 CIRCUIT SATISFIABILITY
• CIRCUIT-SAT: Given a combinational circuit built out
of 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 ? ? ?

hard-coded inputs inputs

THE “FIRST” NP-COMPLETE PROBLEM
• Theorem: CIRCUIT-SAT is NP-complete!
◦ [Cook 1971, Levin 1973]
• Proof (sketch):
◦ Any algorithm that takes a fixed number of bits P as
input and produces a yes/no answer can be
represented by such a circuit. Moreover, if
algorithm takes poly-time, then circuit is of poly-
size.
◦ Natural: Algorithms are implemented on computers
(i.e. on literal circuits)
• Sketchy part of proof: Algorithms typically have no
trouble dealing with inputs of larger size (i.e. more than _
bits), as opposed to circuits.
THE “FIRST” NP-COMPLETE PROBLEM
• Consider some problem Q in NP, with a
polytime certifier K(M, O)
• To determine whether M is in Q need to
know if there exists a O of length g(|M|) such
that K M, O = Oijf
• View K(M, O) as an algorithm on M + g( M )
bits, and convert it into a circuit l"
◦ First |X| bits are hard-coded to X
• l" satisfiable if and only if there exists a
length g( M ) input string such that K M, O =
Oijf
 EXAMPLE
• l" satisfiable iff there exists an IS of size 2
independent set of size 2?
Ù
independent set?
¬
e
hav
ed
g e Ú
e set of size 2?
som
of G = (V, E), n = 3
i nts Ú
po
e nd en? Ú
th os
bo n ch
e
be Ù Ù Ù u
Ú

v w
Ù Ù Ù

u-v u-w v-w u v w

1 0 1 ? ? ?
ænö
ç ÷ hard-coded inputs (graph description) n inputs (nodes in independent set)
è2ø
 ESTABLISHING NP-COMPLETENES
• Once we have the first NP-Complete problem,
others fall like dominoes
◦ We have hundreds (if not thousands) of known NP-
complete problems!
• Recipe to establish NP-completeness for i
◦ Step 1: Show that ! is in NP (the step that most
students forget)
◦ Step 2: Choose an NP-complete problem E
◦ Step 3: Prove that E ≤" !
• Proof: Let k be any problem in db
◦ ] ≤" E ≤" !
◦ Hence ! is NP-complete
 THEOREM: 3-SAT IS NP-COMPLETE
• Proof:
◦ We’ve seen that 3-SAT is in NP, so it suffices to show
that CIRCUIT-SAT ≤" 3-SAT
◦ Let c be any circuit
◦ Create a 3-SAT variable d# for every element of c
• `! = ¬`" → add two clauses (`! ∨ `" ), (`! ∨ `" )
– Can’t set both to true or both to false!
• `# = `$ ∨ `% → add three clauses (`# ∨ `$ ), (`# ∨ `% ),
(`# ∨ `$ ∨ `% )
– If 5! is true, at least one of 5" and 5# has to be true. If 5! if false,
both 5" and 5# have to be false
• `# = `$ ∧ `% → add three clauses (`$ ∨ `# ), (`% ∨ `# ),
(`# ∨ `$ ∨ `% )
– If 5! is true, at both of 5" and 5# have to be true. If 5! if false, at
least one of 5" and 5# has to be false
 THEOREM: 3-SAT IS NP-COMPLETE

• Proof (continued):
◦ Hard-coded input and output values
• $- = 0 → add clause $-
• $. = 1 → add clause ($.)

output
x0
Ù
x1 x2 !! ∧ (!" ∨ !# ) ∧ (!" ∨ !! ) ∧ (!" ∨ !# ∨ !! ) ∧(!$ ∨
Ú ¬ !% ) ∧ !$ ∨ !% ∧(!" ∨ !& ) ∧ (!$ ∨ !& ) ∧ (!& ∨ !" ∨ !$ )

x5 x4 x3
0 ? ?
 NP-COMPLETENESS
• Observation. All problems below are NP-complete
and polynomial reduce to one another!
CIRCUIT-SAT

3-SAT

to
du ces SET
re EN T
AT D
3-S DEPEN
IN

INDEPENDENT SET DIR-HAM-CYCLE GRAPH 3-COLOR SUBSET-SUM

VERTEX COVER HAM-CYCLE PLANAR 3-COLOR SCHEDULING

SET COVER TSP

 NP-COMPLETE PROBLEMS

• Basic big “genres” of NP-complete problems:

◦ Packing: SET-PACKING, INDEPENDENT SET
◦ Covering: SET-COVER, VERTEX-COVER
◦ Constraint Satisfaction: 3-SAT, CIRCUIT-SAT
◦ Partitioning: COLORING, 3-D MATCHING
◦ Numerical problems: SUBSET-SUM, KNAPSACK
◦ Sequencing: HAMILTONIAN CYCLE, TSP
 NP-COMPLETE PROBLEMS

• In practice, most problems are either in P or

known to be NP-complete
• There are important exceptions:
◦ Factoring
◦ Graph isomorphism
◦ Finding a Nash-equilibrium
 EXTENT AND IMPACT
• “Prime intellectual export of CS to other disciplines”
• Thousands of citations every year
◦ More than “compilers” or “database”, etc
• Broad applicability and classification power
• “Captures vast domains of computational, scientific,
mathematical endeavors, and seems to roughly
delimit what mathematicians and scientists had
been aspiring to compute feasibly.”
• A guide to scientific inquiry
◦ E.g. Ising’s phase transition model for 3 dimensions
◦ Top theoreticians searched for an analytical three-
dimensional solution for many decades
◦ Istrail showed that the problem is NP-complete in 2000.
 CO-NP AND THE ASYMMETRY OF NP
• Important detail about NP: We only need certificates
for UVW instances

• Example 1: SAT versus TAUTOLOGY

◦ Can prove that a CNF formula is satisfiable by giving a
satisfying assignment
◦ How could you prove that a formula is not satisfiable?

• Example 2: HAM-CYCLE versus NO-HAM-CYCLE

◦ Can prove that a graph is Hamiltonian by giving a
Hamiltonian cycle
◦ How could we prove that a graph is not Hamiltonian?
 CO-NP AND THE ASYMMETRY OF NP

• NP: Decision problems for which there is a

poly-time certifier
• Definition: Given a decision problem Q its
complement Qp is the same problem, but
with efM and qr instances reversed
◦ I.e. X ∈ \o iff X ∉ \
• co-NP: Decision problems whose
complement is in NP
 NP VERSUS CO-NP
• Fundamental question: Does NP = co-NP?
◦ Do _`X instances have succinct certificates iff qr
instances have succinct certificates?
◦ Probably not…
• Theorem: If _^ ≠ ur-_^ then ^ ≠ _^
◦ Proof idea:
◦ t is closed under taking complements
◦ If t = ut, then ut is closed under taking
complements
◦ Therefore, ut = vr-ut
◦ This is the contrapositive of the theorem
 PROBLEMS NP ∩ CO-NP
• Example: Given a bipartite graph, does it have a perfect
matching:
◦ If $%": can exhibit a perfect matching
◦ If _f: can exhibit a set of nodes g, s.t. \ g < |g|
• Every problem in :; ∩ =>-:; has a “good
characterization”
◦ Short proof for $%" and short proof for _f
• Observation: ; ⊆ :; ∩ =>-:;
• Fundamental open question: Does P equal NP ∩ co-NP?
◦ Mixed opinions
◦ Many examples where problems had good characterizations
first, and then years later an efficient algorithm was
developed
• E.g. linear programming, primality testing
• E.g. Factoring is in :; ∩ =>-:; but not known to be in P
 SUMMARY

• Definition of NP (8.3 in KT)

• NP-Completeness (8.4 in KT)
• co-NP (8.9 in KT)