程序代写代做代考 algorithm Microsoft PowerPoint – lecture22 [Compatibility Mode]

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  y1y2 …yi. (x,y1,…,yi)R 

y1y2 …yiz. 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  y1y2 … yi. (x,y1,…,yi)R 
y1y2 … 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

NPP/poly  PH collapses to 2nd level

• NPP/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. NPP/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. NPP/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 NPP/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.