Microsoft PowerPoint – lecture16 [Compatibility Mode]
1
COMS4236: Introduction to
Computational Complexity
Spring 2018
Mihalis Yannakakis
Lecture 16, 3/8/18
Outline
• Problems with numbers
– strong vs. weak NP-hardness
– pseudopolynomial algorithm
• coNP
• NPcoNP
• Factoring
2
Subset Sum
• Input: set S of (positive) integers, another integer t
• Question: subset T of S that sums to t?
• Note: numbers given in binary
• There is a pseudopolynomial algorithm: runs in time
polynomial in the value of the numbers (not the bit-size)
• A problem is called strongly NP-complete if it is NP-
complete even if the numbers are given in unary notation
instead of binary.
• Subset Sum is not strongly NP-complete.
• It is weakly NP-complete
Subset Sum
• Input: set S of (positive) integers, another integer t
• Question: subset T of S that sums to t?
• Note: numbers given in binary
• In NP: certificate = subset T
• NP-hard: Reduction from Node Cover
• Given graph G=(N,E), bound k for Node Cover instance
of Subset Sum where S has one integer ai for every node i
of G, and one integer bij for every edge (i,j) of G.
• If G has e edges, then each integer has 2e+1 bits
e 1
e i
i 0
Target number t k 4 2 4
3
Node Cover ≤log Subset Sum
2e+1 bits: leading bit + 2 bits per edge (edges in any order)
Leading bit= 1 for node-numbers ai, 0 for edge-numbers bij
ai: 1 — — — 00 01 — —
bij: 0 00 .. .. 00 01 ….
01 if i edge, 00 otherwise
All 0 except 01 at edge (i,j)
t: bin(k) 10 10 10 10 10 Target t = k in binary followed by
10 for all edges
• For any subset T, when we add up the numbers in T,
there is no carry from bits of one edge to the next or to the
leading bit, because only three numbers have a 1 in the 2
bits for an edge
edge bits:
Example
6
1
2
3
4 (1,2) (1,3) (2,3) (2,4) (3,4)
a1: 1 0 1 0 1 0 0 0 0 0 0
a2: 1 0 1 0 0 0 1 0 1 0 0
a3: 1 0 0 0 1 0 1 0 0 0 1
a4: 1 0 0 0 0 0 0 0 1 0 1
b12: 0 0 1 0 0 0 0 0 0 0 0
b13: 0 0 0 0 1 0 0 0 0 0 0
b23: 0 0 0 0 0 0 1 0 0 0 0
b24: 0 0 0 0 0 0 0 0 1 0 0
b34: 0 0 0 0 0 0 0 0 0 0 1
k =3
Graph G:
Target number t: 1 1 1 0 1 0 1 0 1 0 1 0
edges
4
Node Cover ≤log Subset Sum
• If node cover C with k nodes then subset T of S that
sums to t
• T = { ai | i C } { bij | iC or j C } sums to t
• If subset T of S that sums to t then node cover C with k
nodes
• Because there is no carry from bits of one edge to the next
and t has 10 for all edges, T must contain for each edge (i,j)
at least one of ai, aj
• Because of the k in the leading bits of t, T must contain
exactly k numbers ai C = { i | ai T} is a node cover of
size k
0-1 Knapsack
Input: integers v1,…,vn, w1,…,wn (values, weights of the
items), W (knapsack capacity), bound b on total value
Question: subset C{1,…,n} s.t. w(C)≤W and v(C)≥b ?
Reduction from Subset Sum
Instance S={s1,…,sn}, t of Subset Sum
instance of 0-1 Knapsack: n items, vi =wi = si,
knapsack capacity W=t, value bound b=t
• subset T of S that sums to t iff
subset C{1,…,n} s.t. w(C)≤W and v(C)≥b
5
0-1 Integer Linear Inequalities
• Input: Set of linear inequalities
• Question: Is there a 0-1 assignment to the variables that
satisfies the inequalities?
• In NP: Certificate = satisfying assignment
• Integer Linear Inequalities ( integer solution? not only 0-1)
also in NP: if there is an integer solution to a set of linear
inequalities, then there is one of size (#bits) polynomial in
the input size (not trivial to show)
• NP-complete
• Subset Sum: Is there 0-1 solution to s1x1 + … snxn = t ?
• But even strongly NP-complete.
Node Cover ≤log 0-1 Integer Linear Inequalities
• Given graph G and bound k construct instance of 0-1 ILE
– one variable xi for each node i of G
– inequalities xi+ xj 1 for each edge (i,j) of G
– inequality xi k
• 1-1 correspondence between subsets of nodes and 0-1
assignments (=characteristic vectors of subsets)
• A subset covers all the edges and has size k iff the
corresponding 0-1 assignment satisfies all the inequalities
• Corollary: Integer Linear Inequalities also NP-complete
• Proof: Add the inequalities xi 0 and xi 1 for all i
6
Class coNP
• Definition of NP is nonsymmetric with respect to Yes, No
coNP { L | L * L NP }
• A decision problem is in coNP if the complement of its
Yes language L is in NP its No language (set of No
instances) is in NP
Certificate version
A language L is in coNP if there is a polynomial-time
decidable binary predicate R(.,.) and constant c such that
L = { x | y. |y| |x|c predicate R(x,y) is true }
coNP-complete problems
• Complements of NP-complete problems
• UNSAT: Given Boolean formula, is it unsatisfiable?
• TAUTOLOGY (VALIDITY): Given Boolean formula, is it a
tautology (valid), i.e. satisfied by all truth assignments?
• NONHAMILTONICITY: Given a (undirected or directed)
graph, is it nonHamiltonian?
• NON 3-COLORABILITY: Given an undirected graph, is it
the case that it has no 3-coloring?
• NODE COVER LOWER BOUND: Given graph G and
number k, does every node cover of G have ≥k nodes?
• INDEPENDENT SET UPPER BOUND: Given a graph G
and number k, does every independent set of G have ≤k
nodes?
7
Properties
•PNP, PcoNP , thus, PNPcoNP
• NP is closed under union, intersection
• coNP is also closed under union, intersection
• NP (and coNP) closed under complement iff NP=coNP
– conjectured not
Relations between P, NP, coNP
P
NP coNPNPcoNPConjectured
relation:
Other possibilities: NP coNP
NPcoNP
P =
all distinct
P
NP = coNP
P=NP=coNP
8
Fundamental Questions
• P = NP?
Is it always as easy to generate a proof as it is to check a
proof that is given to us?
• NP = coNP?
Is it always possible to provide simple convincing evidence
that something does not exist, as it is to show that
something exists by exhibiting it?
• P = NP∩coNP?
If there is a simple convincing proof both for the presence
and the absence of a property, does this mean we can test
the property efficiently?
Relations between P, NP, coNP and
their complete problems
P
NP coNP
NPcoNP
Conjectured
relation:
all distinct
NPC coNPC
• If an NP-complete problem is in P then P=NP
• If an NP-complete problem is in coNP then NP=coNP
If NP¹coNP then no NP-complete problem can be in coNP
– equivalently, no problem in NP∩coNP can be NP-complete
9
NP∩coNP
• Short, easy to check certificates both for the Yes and the
No instances
• Examples:
• Graph Bipartiteness:
– bipartite nodes can be partitioned into two sets V1, V2 so that
all edges connect a node in V1 with a node in V2
– nonbipartite there is an odd length cycle
• Graph Planarity
– planar can draw on the plane so that no edges intersect
– nonplanar contains a homeomorph of K5 or K33 (Kuratowski’s
theorem)
K5 K33
• These particular properties happen to be in fact in P
NP∩coNP and Optimization
• Optimization problems whose decision version is in NP:
assume solutions have polynomial size (#bits) and cost
(or values) can be computed in polynomial time
• If there is a polynomial time (or even NP) optimality
testing algorithm, which, given an instance and a solution,
tests that the solution is optimal, then the decision version
is in coNP, and hence probably not NP-complete.
• Proof: Given an instance x and a bound k, guess a
solution s, verify that it is optimal, and verify that its cost
(or value) is worse than k (i.e. cost(s) >k for a
minimization problem, or value(s)
p divides N
• Decision ÎcoNP: Guess the prime factorization of N:
, verify the factoring and primality of the pi
(can use the primality algorithm in P or the NP algorithm:
guess certificates C(pi) for all the pi and verify them)
Check that no pi is b
• If NP∩coNP=P then Factoring Decision P Factoring P
• In other words, Factoring P NP∩coNP¹P
• Factoring can be done in polynomial time in a Quantum
Computer model [Shor 1994] – more powerful than ordinary
computers?
1 21 2 k
i i i
kN p p p
Hardness of Factoring ?
• Probably cannot use NP-hardness to argue that Factoring is
an intractable problem:
• If Factoring is NP-hard then NP=coNP
• This holds even for a more general notion of polynomial
reduction (and NP-hardness) called Cook reduction.
• Problem A Cook reduces to problem B if there is an
algorithm for problem A that uses a subroutine for B and
which runs in polynomial time apart from the subroutine calls
Thus if the subroutine for B is polynomial-time then the
algorithm A also polynomial-time.
• If SAT Cook reduces to Factoring then can get NP algorithm
for UNSAT (a coNP-complete problem): replace the
subroutine calls with an NP algorithm that guesses and
verifies the factorization.
12
NP∩coNP and Completeness
• Factoring P NP∩coNP¹P
• Does the converse hold?
Can we argue that Factoring is complete for NP∩coNP?
• No complete problems known for NP∩coNP
• Basic Obstacle: NP∩coNP is a “semantic class”.
• No effective syntactic characterization in terms of a class
of machines, as we had with deterministic and
nondeterministic time- and space-complexity classes,
where we could just limit the amount of time or space
used by a TM