P, NP, and PH
1 Introduction to NP Recall the definition of the class P:
Def 1.1 A is in P if there exists a Turing machine M and a polynomial p such that ∀x
• Ifx∈AthenM(x)=YES.
• Ifx∈/AthenM(x)=NO.
• For all x M(x) runs in time ≤ p(|x|).
The typical way of defining NP is by using non-deterministic Turing machines. We will NOT be taking this approach. We will instead use quantifiers. This is equivalent to the definition using nondetermism.
Def1.2 AisinNPifthereexistsasetB∈Pandapolynomialpsuchthat L = {x | (∃y)[|y| = p(|x|) ∧ (x, y) ∈ B]}.
2
Here is some intution. Let A ∈ NP.
•
•
If x ∈ A then there is a SHORT (poly in |x|) proof of this fact, namely y, such that x can be VERIFIED in poly time. So if I wanted to convince you that x ∈ L, I could give you y. You can verify (x, y) ∈ B easily and be convinced.
Ifx∈/AthenthereisNOproofthatx∈A. NP Completeness
Def 2.1 A reduction (also called a many-to-one reduction) from a language L to a language L′ is a polynomial-time computable function f such that x ∈ L iff f(x) ∈ L′. We express this by writing L ≤pm L′.
It may be verified that all the above reductions are transitive.
1
2.1 Defining NP Completeness
With the above in place, we define NP-hardness and NP-completeness:
Def 2.2 A language L is NP-hard if for every language L′ ∈ NP, there is a reduction from L′ to L. A language L is NP-complete if it is NP-hard and also L ∈ NP.
We remark that one could also define NP-hardness via Cook reductions. However, this seems to lead to a different definition. In particular, oracle access to any coNP- complete language is enough to decide NP, meaning that any coNP-complete language is NP-hard w.r.t. Cook reductions. On the other hand, if a coNP-complete language were NP-hard w.r.t. reductions, this would imply NP = coNP (which is considered to be unlikely).
We show the “obvious” NP-complete language:
Theorem 2.3 Define language L via:
M is a non-deterministic T.M.
L = ⟨M, x, 1t⟩ | which accepts x within t steps . Then L is NP-complete.
Proof: It is not hard to see that L ∈ NP. Given ⟨M,x,1t⟩ as input, non- deterministically choose a legal sequence of up to t moves of M on input x, and accept if M accepts. This algorithm runs in non-deterministic polynomial time and decides L.
To see that L is NP-hard, let L′ ∈ NP be arbitrary and assume that non- deterministic machine ML′ ′ decides L′ and runs in time nc on inputs of size n. Define function f as follows: given x, output ⟨ML′ ′ , x, 1|x|c ⟩. Note that (1) f can be computed in polynomial time and (2) x ∈ L′ ⇔ f(x) ∈ L. We remark that this can be extended to give a Levin reduction (between RL and RL′ , defined in the natural ways).
3 More NP-Compete Languages
It will be nice to find more “natural” NP-complete languages. The first problem we prove NP-complete will have to use details of the machine model- Turing Machines. All later results will be reductions using known NP-complete problems.
Def 3.1 1. SAT is the set of all boolean formulas that are satisfiable. That is, φ(⃗x) ∈ SAT if there exists a vector ⃗b such that φ(⃗b) = TRUE.
2. CNFSAT is the set of all boolean formulas in SAT of the form C1 ∧ ··· ∧ Cm where each Ci is an ∨ of literals.
2
3. k-SAT is the set of all boolean formulas in SAT of the form C1 ∧···∧Cm where each Ci is an ∨ of exactly k literals.
4. DNFSAT is the set of all boolean formulas in SAT of the form C1 ∨ ··· ∨ Cm where each Ci is an ∧ of literals.
5. k-DNFSAT is the set of all boolean formulas in SAT of the form C1 ∨···∨Cm where each Ci is an ∧ of exactly k literals.
The following was proven by Stephen Cook and Leonid Levin independently around 1970.
Theorem 3.2 CNFSAT is NP-complete.
Proof: It is easy to see that CNFSAT ∈ NP. Let L ∈ NP. We show that L ≤pm CNFSAT. M be a TM and p, q be polynomials such that
L = {x | (∃y)[|y| = q(|x|) AND M(x,y) = 1]}
and M(x,y) runs in time q(|x|+|y|). WewillactuallyhavetodealwiththedetailsoftheM. LetM =(Q,Σ,δ,Σ,δ,q0,h) We will also need to represent what a Turing Machine is doing at every stage. The machine itself has a tape, something like
#abba#ab@ab#a
(We assume that everything to the right that is not seen is a #. Our convention is that you CANNOT go off to the left— from the left most symbol you can’t go left.)
is in state q and the head is looking at (say) the @ sign. We would represent this
#abba#ab(@, q)a
That is our convention— we extend the alphabet and allow symbols Σ × Q. The symbol (@,q) means the symbol is @, the state is q, and that square is where the head of the machine is.
If x ∈ L then there is a y of length q(|x|) such that the Turing machine on M accepts.
Lets us say that with more detail.
If x ∈ L then there is a y and a sequence of configurations C1,C2,…,Ct such that
• C1 is the configuration that says ‘input is x#y, and I am in the starting state.’ • For all i, Ci+1 follows from Ci (note that M is deterministic) using δ.
3
• Ct is the configuration that says “END and output is 1” • t = p(|x| + q(|x|).
How to make all of this into a formula?
KEY 1: We will have a variable for every possible entry in every possible configura- tion. Hence the variables are zi,j,σ where 1 ≤ i,j ≤ t, and σ ∈ Σ ∪ Q. The intent is that if there is an accepting sequence of configurations then
zi,j,σ = T iff the j symbol in the ith configuration is σ.
To just make sure that for every i, j there is a unique σ such that zi,j,σ = T we have, for every 1 ≤ i ≤ j, the following clauses.
zi,j,σ σ∈Σ∪Q
(NOTE- the actual formula would write out all of this and not be allowed to use . With Poly time it MATTERS what kind of representation you use since we want computations to be poly time in the length of the input.)
for each σ ∈ Σ ∪ (Σ × Q)
zi,j,σ → ¬zi,j,τ
τ ∈(Σ∪(Σ×Q)−{σ}
(It is an easy exercise to turn this into a set of clauses.)
KEY 2: The parts of the formula that say that C1 is the starting configuration for x#y on the tape, and Ct is the configuration for saying DONE and output is 1, are both easy. Note that for the y part- WE DO NOT KNOW y. So we have to write that the y is a squence of elements of Σ of length q(|x|).
Recall our convention for the first and last configuration:
Intuitively we start out with x and y laid out on the tape, and the head looking at the # just to the right of y. The machine then runs, and if it gets to the qaccept state then it accepts.
The following formula says that C1 says ‘start with x’ Let x = x1 · · · xn. z1,1,x1 ∧···z1,n,xn ∧x1,n+1,#∧
n+q(|x|+1
z1,i,σ
i=n+2 σ∈Σ
t(n)
∧z1,q(n)+n+2,(#,s) ∧ ∧z1,i,# i=q(n)+n+3
Note that this formula is in CNF-form.
The following formula says that Ct says ‘ends with accept’
4
t(n)
zt,i,(σ,qaccept
i=1 σ∈Σ
KEY 3: How do we say that going from Ci you must goto Ci+1. We first do a
thought experiment and then generalize. What if δ(q, a) = (p, b).
Then if the Ci says that you are in state q and looking at an a then Ci+1 must be in state p and overwrite a with b. Note that in both cases the rest of the configuration has not changed.
How do we make this into a formula? The statement “Ci says that you are in state q and looking at an a” and the head is at the jth position is
zi,j,(a,q)
We also have to know what else is around it. Assume that there is a b on the left
and a c on the right. So we have
(zi,j−1,b ∧ (zi,j,(a,q) ∧ (zi,j+1,c.
The statement that Ci+1 is in state p and having overwritten a with b (zi+1,j−1,b ∧ (zi+1,j,(b,p) ∧ (zi+1,j+1,c.
This leads to the formula
t
(zi,j−1,b ∧ (zi,j,(a,q) ∧ (zi,j+1,c → (zi+1,j−1,b ∧ (zi+1,j,(b,p) ∧ (zi+1,j+1,c.
i,j =1
This formula can be put into CNF-form.
For all of the δ values we need a similar formula. PUTTING IT ALL TOGETHER
Take the ∧ of the formulas in the last three KEY points and you have a formula φ
x∈L ⇐⇒ φ∈CNFSAT.
5
4 Other NP-Complete Problems
Now that we have SAT is NP-Complete many other problems can be shown to be NP-complete. They come from many different areas of computer science and math: graph theory, scheduling, number theory, and others.
There are literally thousands of natural and distinct NP-complete problems!
5 Relating Function Problems to Decision Prob- lems
Consider the NP-complete problem
CLIQUE = {(G,k) | G has a clique of size k}.
Note that while this is a nice problem, its not quite the one we really want to solve. We want to compute the function
SIZECLIQUE(G) = k such that k is the size of the largest clique in G.
Or we may want to compute
FINDCLIQUE(G) = the largest clique in G (Note- this is ambiguous as there
could be a tie. This can be resolved in several ways.) How hard are these problems?
Theorem 5.1 CLIQUE and FINDCLIQUE are Cook-equivalent. In particular 1. CLIQUE can be solved with one query to FINDCLIQUE.
2. FINDCLIQUE(G) can be computed with logn queries to CLIQUE
Proof:
The first part is trivial.
We give an algorithm for the second part.
1. Input G
2. Ask (G,n/2) ∈ CLIQUE? If YES then ask (G,3n/4) ∈ CLIQUE. If NO then
ask (G,n/4) ∈ CLIQUE.
3. Continue using binary search until you get to the answer. This will take log n
queries.
The theorem above can be generalized to saying that if L ∈ NP then the function associated to it (this can be done in several ways) is Cook Equivalent to L. Details will be on a HW.
6
6 The Polynomial Hierarchy
Recall (one of) the definitions of NP.
Def 6.1 A ∈ NP if there exists a polynomial p and a polynomial predicate B such that
A = {x | (∃y)[|y| ≤ p(|x|) ∧ B(x, y)]}.
What if we allowed more quantifiers? Then what happens?
Notation 6.2
1. The expression
A = {x | (∃py)[B(x, y)]}
means that there is a polynomial p such that A = {x | (∃y, |y| ≤ p(|x|))[B(x, y)]}.
2. The expression
A = {x | (∀py)[B(x, y)]
means that there is a polynomial p such that A = {x | (∀y, |y| ≤ p(|x|))[B(x, y)]}.
3. The expression
A = {x | (∀py)(∃pz)[B(x, y, z)]
means that there are polynomials p1,p2 such that
A = {x | (∀y, |y| ≤ p1(|x|))(∃z, |z| ≤ p2(|x|))[B(x, y, z)]}.
4. One can define this notation for as long a string of quantifiers as you like. We leave the formal definition to the reader.
In the following definition we include a definition and an alternative definition.
Def 6.3
1. A∈Σp0 ifA∈P. A∈Πp0 ifA∈P. (Weincludethissoweuseitinductively later.)
2. A∈Σp1 ifthereexistsasetB∈Psuchthat A = {x | (∃py)[B(x, y)]}.
This is just NP.
7
3. A∈Πp1 ifthereexistsasetB∈Psuchthat
A = {x | (∀py)[B(x, y)]}.
This is just all sets A such that A ∈ NP. It is often called co-NP.
4. A∈Σp2 ifthereexistsasetB∈Psuchthat A = {x | (∃py)(∀pz)[B(x, y, z)]}.
5. A ∈ Σp2 (alternative definition) if there exists a set B ∈ Πp1 such that A = {x | (∃py)[B(x, y)]}.
6. A∈Πp2 ifthereexistsasetB∈Psuchthat A = {x | (∀py)(∃pz)[B(x, y, z)]}.
7. A ∈ Πp2 (alternative definition) if A ∈ Σp2.
8. Leti∈N. IfiiseventhenA∈Σpi ifthereexistsB∈Psuchthat A = {x | (∃py1)(∀py2)···(∀pyi)[B(x,y1,…,yi)] IfiisoddthenA∈Σpi ifthereexistsB∈Psuchthat
A = {x | (∃py1)(∀py2)···(∃pyi)[B(x,y1,…,yi)]
9. Leti∈N. IfiiseventhenA∈Πpi ifthereexistsB∈Psuchthat A = {x | (∀py1)(∃py2)···(∃pyi)[B(x,y1,…,yi)] IfiisoddthenA∈Πpi ifthereexistsB∈Psuchthat
A = {x | (∀py1)(∃py2)···(∀pyi)[B(x,y1,…,yi)]
10. Let i ∈ N and i ≥ 1. A ∈ Σpi (alternative definition) if there exists B ∈ Πpi−1 such that
A = {x | (∃py)[B(x, y)]}.
(Note- we use the definition of Σp0, Πp0 here.)
11. A ∈ Πpi (alternative definition) if A ∈ Σpi .
12. The polynomial hierarchy, denoted PH, is ∞i=0 Σpi . Note that this is the same
as ∞i=0 Πpi .
Def 6.4 A set A is Σpi -complete if both of the following hold. 1. A ∈ Σpi , and
2. ForallB∈Σpi,B≤pm A.
8
Def 6.5 A set A is Πpi -complete if both of the following hold. 1. A ∈ Πpi , and
2. ForallB∈Πpi,B≤pm A.
Def 6.6 A set A is Πpi -complete (Alternative Definition) if A is Σpi -complete.
Example 6.7 In all of the examples below x and y and xi are vectors of Boolean variables.
1. A = {φ(x,y) | (∃b)(∀c)[φ(b,c)]}. This set is Σp2-complete. It is clearly in Σp2. This is called QBF2. The QBF stands for Quantified Boolean Formula. The proof that it is Σp2-complete uses Cook-Levin Theorem.
2. One can define QBFi easily. It is Σpi -complete.
3. QBF is the set of all φ(x1, . . . , xn) (the xi’s are vectors of variables) such that (∃x1)(∀x2)···(Qxn)[φ(x1,…,xn)]. (Q is ∃p if n is odd and is ∀p if n is even.) This set is thought to not be in any Σpi or Πpi .
4. Let T W O = {φ | φ has exactly two satisfying assignments }. We show that T W O ∈ Σ p2 .
TWO =
{φ | (∃b, c)(∀d)[b ̸= c ∧ φ(b) ∧ φ(c) ∧ (φ(d) → ((d = b) ∨ (d = c)))}
It is not known if TWO is Σp2-complete; however it is thought to NOT be.
5. One can define THREE, FOUR, etc. easily. They are all in Σp2.
6. One can define variants of T W O having to do with finding TWO Hamiltonian
cycles, TWO k-cliques, etc. Also THREE, etc. These are all Σp2.
7. ODD = {φ | φ has an odd number of satisfying assignments } is thought to
NOT be in PH.
Recall that
There are literally thousands of natural and distinct NP-complete problems!
What about Σp2-complete problems? Other levels? Alas- there are very few of these. So why do we care about PH ?
We think that SAT ∈/ P since
SAT ∈P→P=NP.
We tend to think that PH does not collapse to a lower level of the hierarchy (e.g., that PH = Σp2 ). Hence if we have a statement XXX that we do not think is true but cannot prove is false, we will be happy to instead show
XXX → PH collapses . 9
7 Collapsing PH
Theorem 7.1 If Πp1 ⊆ Σp1 then PH = Σp1 = Πp1.
Proof: Assume Σp1 = Πp1. We first show that Σp2 = Σp1. LetL∈Σp2. HencethereisasetB∈Πp1 suchthat
L = {x | (∃py)[(x,y) ∈ B]}.
Since B ∈ Πp1 , by the premise B ∈ Σp1 . Therefore there exists C ∈ P such that
B = {(x,y) | (∃pz)[(x,y,z) ∈ C]}. Replacing this definition of B in the definition of L we obtain
L = {x | (∃py)(∃pz)[(x, y, z) ∈ C]}.
This is clearly in Σp1 . Hence Σp2 ⊆ Σp1 . Hence we have Σp2 = Σp1 . By complementing both sides we get Πp2 = Πp1.
One can now easily show that, for all i, Σpi = Σp1 by induction. One then gets Πpi =Πp1.HencePH=Πp1=Σp1.
The following theorems are proven similarly Theorem7.2 Leti∈N. IfΠpi ⊆Σpi thenPH=Σpi =Πpi.
Theorem 7.3 If Σpi ⊆Πpi then PH=Σpi =Πpi.
10