Microsoft PowerPoint – lecture21 [Compatibility Mode]
COMS4236: Introduction to
Computational Complexity
Spring 2018
Mihalis Yannakakis
Lecture 21, 4/3/18
Outline
• Relativization: Oracle B s.t. PB = NPB
• PNP, FPNP
• NPNP
• Polynomial Hierarchy (PH)
• P = NP PH = P
• i = i PH collapses to i = i
P vs NP and Relativization
1. There is an oracle A such that
2. There is an oracle B such that
Methods that relativize cannot resolve the P vs. NP
question one way or the other.
Part 1: Showed it last time.
A AP NP
B BP NP
• For any oracle B {0,1}*, define the language
LB = { 0ⁿ | xÎB s.t. |x|=n }
• For any B,
– Given a string 0ⁿ , guess a binary string x of the same
length, query if it is in B, and if it is then accept.
• We’ll define a B such that LB differs from the language of
any P-time machine with oracle B
• Enumerate P-time oracle machines M1, M2, … and
assume wlog that Mi runs in time at most ni
• We’ll define B in stages, where stage i kills machine Mi
• Before each stage i, we have specified for a finite set Si
of strings whether they are in B or not.
B BP NP for some oracle B
BBL NP
• Stage i. Take n large enough so that it exceeds the
length of all strings in Si and also
• Run Mi on input 0ⁿ. If it queries a string in Si answer
accordingly; if it queries another string answer No (B).
• At the end, if Mi accepts 0ⁿ, then specify that all
(remaining) strings of length n are not in B
• If Mi rejects 0ⁿ, then pick a string z of length n that Mi has
not queried and add it to B ; such a string z exists
because
• Mi does the wrong thing on input 0ⁿ
it does not accept LB
If a string x is not specified in any stage then arbitrarily let
xB (it does not matter).
B BP NP for some oracle B
2i nn
2i nn
Relativization results for other relations
• Similar relativization results can be shown for essentially
all possible relationships between various classes (P, NP,
coNP, RP, BPP,…) that we do not know currently how they
relate. For example:
• There is an oracle A relative to which NP=coNP and an
oracle B relative to which NP≠coNP
• There is an oracle A relative to which P=NPcoNP but
P≠NP, P≠coNP
• etc.
Beyond NP and coNP
• There are various types of problems, that do not seem to
be in NP or coNP, though they are closely related to NP
problems.
• Exact Optimal Value Problems
• Example: Exact Maximum Clique problem
• Input: Graph G, number k
• Question: Does the maximum clique of G have exactly k
nodes?
• Exact Min TSP cost
• Input: Distances {dij} between n cities, value b
• Question: Does the optimal tour have cost exactly b?
HW : Show they are not in NP or coNP unless NP=coNP
Exact Optimum Value Problems
• Involve two questions, one in NP and one in coNP:
1. Is the maximum clique k? (in NP: clique of size k?)
2. Is the maximum clique ≤k? (in coNP: cliques size ≤k?)
1. Is the minimum TSP cost ≤b? (in NP)
2. Is the minimum TSP cost b? (in coNP)
• Can be solved by a Ptime oracle TM with an oracle for
the Clique decision problem (or any other NP-complete
problem), i.e. in PNP
• but makes very little use of the oracle: only two queries
Other Types of Problems
• Critical Instance problems (eg, “ minimal forbidden
subgraphs”)
• Example: Critical 3-colorability
• Input: Graph G
• Question: Is it is the case that G is not 3-colorable but if
we delete any edge it becomes 3-colorable?
(HW: Show that two queries are sufficient.)
• Unique Solution problems
• Example: Unique SAT
• Input: Boolean formula
• Question: Does have a unique (exactly one) satisfying
truth assignment?
• = class of languages that can be decided in P using
an oracle in NP.
• = class of functions that can be computed in P time
using an oracle in NP. In other words, there is an
algorithm that uses as a subroutine a decision problem
in NP and apart from the subroutine calls, it runs in
polynomial time.
• Example: Optimum value and optimal solutions of NP
optimization problems.
• Compute the size of the maximum clique, compute the
min cost of a TSP tour, …
• Compute a maximum clique, an optimal TSP tour, …
NP NPP and FP
NPP
NPFP
Minimum Size Circuit Problem
• Given a Boolean circuit C, find an equivalent circuit C*
that has minimum size, i.e. C(x)=C*(x) for every input
vector x and C* has the minimum number of gates
• Decision version
• Input: Boolean circuit C, number k
• Question: Is there an equivalent circuit C’ with ≤k gates?
• Why isn’t this problem obviously in NP?
• The equivalence problem, is CC’? is probably not in P.
• In fact even if C is a 3SAT formula and C’ is the trivial
circuit that answers False for every input, CC’? asks if
the formula is unsatisfiable.
Minimum Size Circuit Problem
• The equivalence problem, is CC’?, is in coNP
(Complement is in NP: Guess an input x such that
C(x)¹C’(x).)
• We can solve the decision version of the minimum size
circuit problem with an NP machine that guesses the
circuit C’ and then asks an oracle if CC’? (i.e. a coNP
problem) or equivalently if C¹C’ (a NP problem).
• That is, the decision version of the Minimum Circuit
Problem is in NPNP = NPcoNP
Polynomial Hierarchy PH
• At each level i, a deterministic i) a nondeterministic (i)
and a co-nondeterministic (i) class defined with an
oracle from the previous level
• Level 0: P = 0 = 0 = 0
• Level i+1>0: i
i
i
Σ
i+1
Σ
i+1
Σ
i+1 i+1
P
NP
co = coNP
Example. Level 1: 1 = P; 1 =NP; 1 = coNP
• Polynomial Hierarchy = PH = Union of all these classes
• That is, a language L is in PH if there is some constant i
such that L is in i or is in i or in i
Polynomial Hierarchy PH
• Many authors attach a P in the notation of the classes,
either as a superscript (eg. ) or next to it (eg. in the
book) to differentiate the classes from the “arithmetic or
Kleene hierarchy” (an analogous hierarchy of undecidable
problems)
• Properties
• i = coi for all i (by definition)
• The definitions do not change if we use i instead of i in
the oracles
• Each class at level i contains all the classes in all the
previous levels
•
p
i iP
i i i
i 0 i 0 i 0
PH =
The Lattice of Containments
P
NP∩coNP
1 =NP 1=coNP
2
3
2 2
33
P = NP PH = P
2
2 2
Suppose .
Then NP P
P NP
NP NP NP P
co coP P
i
i
i+1
i+1 i+1
Inductively, assume
Then P
P
NP NP NP P
co coP P
NP = coNP PH =NP
• First show 2 = NP
• Consider a language L in 2 = NPNP
L is decided by a nondetermistic p-time oracle TM M with
oracle A in NP.
ANP=coNP there is an NP machine M1 for A and an
NP machine M2 for it complement Ac
• NP TM M’ for L:
Run M on given input x.
For each query, guess whether the query string wA.
– if guessed ‘yes’ (resp. ‘no’) then run M1 (resp. M2) on w,
and if it accepts then continue else reject (and halt)
If at the end M accepts, then accept, else reject
• x L iff there is an accepting computation
NP = coNP PH =NP ctd.
• 2 = NP 2 = coNP=NP
• Inductively, i = NP i+1 = NPi = NPNP = 2 = NP
i+1 = coNP=NP
i = i PH collapses at i-th level
• If for some i, i = i then all classes at higher levels are
equal to i = i, i.e. the hierarchy collapses at the i-th level
• Proof:
Similar. First show that i+1 i, by a similar proof.
This implies i+1 = coi+1 coi = i = i
Also, i+1 i i+1 i+1 i
Inductively we can show then that all higher levels are also
equal to i :
j i
j i j+1 i+1 iIf then =NP NP