Microsoft PowerPoint – lecture22 [Compatibility Mode]
COMS4236: Introduction to
Computational Complexity
Spring 2018
Mihalis Yannakakis
Lecture 22, 4/4/18
Outline
Polynomial Hierarchy
• Certificate characterization of PH classes
• Complete problems: QSATi
• NP P/poly PH collapses to 2nd level
Certificate (Quantifier) version of the PH
• A (i+1)-ary relation R with arguments x,y1,…,yi is
polynomially balanced if all tuples x,y1,…,yi in R have
|y1|,…,|yi| ≤ p(|x|) for some polynomial p(n).
• Theorem: A language L is in i iff there is a polynomially
balanced and polynomial-time decidable (i+1)-ary
relation R such that
L = { x | y1 y2 …Qiyi such that (x,y1,…,yi) R }
where Qi is if i is odd and if i is even.
(all quantifiers range over strings of length ≤ p(|x|) and alternate
between and , starting with )
Certificate (Quantifier) version of the PH
• A language L is in i iff there is polynomially balanced
and polynomial-time decidable (i+1)-ary relation R such
that L = { x | y1 y2 …Qiyi such that (x,y1,…,yi) R }
where Qi is if i is odd and if i is even.
(all quantifiers range over strings of length ≤ p(|x| and alternate
between and , starting with )
• Note: Level i of the class in the PH = #alternations of
existential and universal quantifiers in the
characterization
• First quantifier is existential for , universal for
Proof of certificate characterization
• Show for 2 .
• Follows then for 2, by complementation, and can
extend inductively to higher levels.
• 1. Suppose L= { x | y1 y2 (x,y1,y2) R }
Oracle NTM M:
On input x, guess a string y1 of length ≤p(n) and ask the
oracle if string y2 of length ≤p(n) such that (x,y1,y2) R
(an NP query).
If the oracle answers No, then accept, else reject.
Note: Only one query to the oracle suffices.
Proof of certificate characterization
• 2. Suppose L is accepted by a NP oracle machine M with
SAT as oracle.
• First, show that L accepted by a NP oracle machine M’ that
makes only one query:
• On input x, M’ guesses an accepting computation of M, i.e.
including all guesses of M, all queries and all answers. For
each Yes answer, M’ guesses a satisfying truth assignment.
For the queries (formulas) 1,…,m with No answer, M’ asks
the SAT oracle if 1… m is satisfiable. If the oracle
answers No, then M’ accepts, else rejects.
• x L iff computation y1 of M’ s.t. truth assignments y2 to
the variables of the formula queried by the computation y1:
y1 is an accepting computation of M’ and the formula
queried by y1 is not satisfied by the truth assignment y2
Proof of certificate characterization
• Similarly can show that L is in i iff there is a polynomially
balanced relation S(.,.) in i-1 such that L= { x | y . (x,y) S}
• The complement of L is { x | y. (x,y) }, thus i is the
class of all languages of the form { x | y. (x,y) } where
is a polynomially balanced relation in i-1
• The certificate/quantifier characterization of i, i follows by
induction.
L
S
S
S
Complete Problems for the levels of PH
• QSATi: Truth of a closed Quantified formula in prenex
normal form (all quantifiers at the beginning) with i quantifier
alternations, starting with an existential quantifier
• Input: Boolean formula with its variables partitioned into i
tuples of variables Y1, Y2, …, Yi
• Question: Is it true that Y1 Y2 … QiYi . Y1,Y2,…,Yi) ?
i.e. there is an assignment to the variables in Y1, such that
for all assignments to the variables in Y2, … the formula
evaluates to true?
(Y1, Y2 etc. is a notational shorthand for the
quantification of all the variables in Y1, Y2 etc )
• Example:
3 alternations Instance of QSAT3
• QSATi is i-complete
1 2 3 4 1 2 3 4 1 2.[( ) (( ( ))]z z z z z z z z z z
Complete Problems
• Q’SATi: Quantified satisfiability with i quantifier
alternations, starting with universal:
Y1 Y2 … Yi . Y1,Y2,…,Yi)
• Q’SATi is i-complete
• Instance Y1 Y2 … Yi . Y1,Y2,…,Yi) of QSAT is false iff
Y1 Y2 … Yi . Y1,Y2,…,Yi) (an instance of Q’SAT) is true
QSATi is i-complete
• QSATi is in i
– QSATi conforms to the quantifier characterization of i
since we can evaluate in poly time for a given truth
assignment
• QSATi is i-hard
• Take a language L in i :
L = { x | y1 y2 …Qiyi . (x,y1,…,yi) R }, for some poly-
balanced and poly-time decidable relation R, where Qi is
if i is odd and if i is even.
• May assume wlog that the input x and the yj are encoded as
binary strings
QSATi is i-complete ctd.
• Suppose i is odd
• Given the input x, we can construct a polynomial-size circuit
C for R: the circuit has (tuples of) inputs x,y1,…,yi .
• C outputs 1 for an input vector iff R(x,y1,…,yi) holds
• From the proof of Cook’s theorem, we can introduce a tuple
z of variables for the gates of the circuit and construct a
formula in the variables x,y1,…,yi ,z, which has the property
that for every input assignment x,y1,…,yi :
C(x,y1,…,yi)=1 z. x,y1,…,yi ,z)
• Thus, (x,y1,…,yi)R z. x,y1,…,yi ,z)
• Therefore xÎL y1y2 …yi. (x,y1,…,yi)R
y1y2 …yiz. x,y1,…,yi ,z)
note: only i alternations instance of QSATi
QSATi is i-complete ctd.
• If i is even (last quantifier in characterization of L is ), then
we construct a circuit C for R and let
• Then C(x,y1,…,yi )=1 (x,y1,…,yi) R
• and C(x,y1,…,yi )=1 z. x,y1,…,yi ,z)
• Thus, (x,y1,…,yi)R z. x,y1,…,yi ,z)
• Therefore xÎL y1y2 … yi. (x,y1,…,yi)R
y1y2 … yi z. x,y1,…,yi ,z)
note: again only i alternations instance of QSATi
If the whole PH has a complete problem
then PH collapses
• If PH has a complete problem L,
then L is at some level i of the hierarchy
• PH collapses at level i
NPP/poly PH collapses to 2nd level
• NPP/poly SAT has a poly-size circuit family (C1,C2, …)
• Assume some standard binary encoding of SAT instances
which respects length order, i.e. if a formula f has fewer
variables and clauses than f’ then |enc(f)| < |enc(f’)|.
• First show: The problem, “given a family of circuits C=(C1,C2,
…,Cn), does it decide correctly SAT instances up to size n?”,
is in coNP, i.e. the question whether the family C is incorrect
is in NP.
NPP/poly PH collapses to 2nd level
• The problem, given a family of circuits C=(C1,C2, …,Cn) does
it decide correctly SAT instances up to size n, is in coNP, i.e.
the question whether the family C is incorrect is in NP.
NP algorithm for testing if C=(C1,C2, …,Cn) is incorrect
• Guess a formula f (certificate= formula of minimum length for
which corresponding circuit C|f|(f) is wrong).
• Pick any variable x, set it to 1 formula f1 ,
and set it to 0 formula f0 .
• Formulas f0, f1 smaller than f evaluated correctly.
• Compare C|f|(f) with C|f0|(f0) C|f1|(f1) . If they are different then
the family is not correct.
NPP/poly PH collapses to 2nd level
• Suffices to show that QSAT3 is in 2. Then 3 2, and the
PH collapses to 2.
• Consider an instance f = Y1 Y2 Y3 . Y1,Y2,Y3) of QSAT3.
• Suppose that C=(C1,C2, …Cn) is a correct circuit family for
SAT for instances up to size n=|f|.
• Every assignment to the variables Y1,Y2, yields a SAT
formula (Y1,Y2) in the variables Y3 by substituting the values
of Y1,Y2 in and simplifying it: (Y1,Y2)Y3) =Y1,Y2,Y3).
• Y3 . Y1,Y2,Y3) holds (Y1,Y2) satisfiable
Ct((Y1,Y2)) =1, where t=|(Y1,Y2)|
• Thus, f is in QSAT3 (f holds) Y1 Y2 Ct((Y1,Y2)) =1
NPP/poly PH collapses to 2nd level
• QSAT3 is accepted by the following NP oracle machine with
an oracle for coNP
On input f = Y1 Y2 Y3 . Y1,Y2,Y3) :
• 1. Guess a circuit family C=(C1,C2, …Cn) of polynomial size
for SAT instances up to size n=|f|.
• Ask the oracle if the circuit family C is correct.
If oracle says No (i.e. C is incorrect), then reject,
else continue (C is correct).
• 2. Guess an assignment for the variables in Y1.
• Ask the oracle if Y2 Ct((Y1,Y2)) =1, where t=|(Y1,Y2)|;
If oracle says Yes then accept, else reject.