1.
The reduction Step 1
let the variable in 3SAT is x1, x2, ….. xn,
we add corresponding variables Y1, Y2, ….. Yn, and add following inequality:
Yi ≥ 0, Yi <=1 for i=1, 2...n.
Step 2
For every clause in 3SAT.
If the literal is Xi, then the corresponding term is Yi,
If the literal is not(Xi), then the corresponding term is (1-Yi).
Add a equality with the sum of three terms greater than 0. For example, the clause is not(X1) ∨ X2 ∨ X3, then we add (1-Y1) + Y2 + Y3 >= 1 .
Obviously, this reduction can be done in polynomial-time.
Now we prove that 3SAT is satisfiable if and only if the resulting inequalities got from above steps has an integer solution.
Prove if 3SAT is satisfiable then the linear inequalities has an integer solution.
Suppose 3SAT has a satisfiable assignment, then if Xi is assigned true, then we set the corresponding Yi to 1, if Xi is assigned false, then we set the corresponding Yi to 0.Now we show that this set of integer values satisfy all the inequality. Obviously inequality from Step 1 is satisfied. For inequalities from step 2, because the 3SAT clause is true, so at least 1 literal is true, thus at least 1 corresponding term in the inequality is 1, because every term is Yi or (1-Yi), every term is >=0, now 1 term is 1, so the sum must >= 1.
Prove if the linear inequalities has an integer solution then 3SAT is satisfiable.
From inequalities from step 1 Yi ≥ 0, Yi <=1 and Yi is an integer, we know that Yi is either 0 or 1. If Yi in the integer solution is 1, then we set Xi to true, if Yi is 0 then we set Xi to false. For each clause in SAT, because the corresponding inequality got from step 2 is >= 1, this means at least 1 term is 1. If the term Yi is 1, then literal Xi is true, if the term (1-Yi) is 1, then the literal not(Xi) is true, so at least 1 literal in the clause is true.
2.
First prove that L is in NP.
Given (M,x,1t) as input, non-deterministically move t steps to generate y, in each step generate 1 or 0, then
simulate M on (x, y), within at most another t steps, accept if M accept. This algorithm runs in non-deterministic polynomial time and decides L, so L is in NP.
Then prove that every A in NP is polynomial time reducible to L.
Assume non-deterministic machine MA decides A and run in time nc on input size n. Define non-deterministic machine MA’ as follows, it accepts
Define the reduction f as follows: given x, output < MA’, x, > .
The f runs in polynomial time and x in A if and only if f(x) in L. So For any language A in NP, it is polynomial time reducible to L.
3.
Let L is a language in NP. Since L is in NP, there is a non-deterministic Turing machine M that decides L in time O(nc). Define language L2 as follows.
where 1 is the symbol not in L.
L2 can be decided in non-deterministic O(n2) as follows. Given input x2, verify that it has the form
O(n2), so L2 in NTIME(n2), if NTIME(n2) ⊆ P , then there is also a deterministic
machine DM that decides L2 in polynomial time, We can then decide L in deterministic
and reject if it does not. If it has the correct form, simulate M(x). The
simulation takes non-deterministic |x|2c, the length of input x2 is |x|c+1, so it takes
polynomial time as follows. Given input x, simulate . This takes only polynomial time in the size of x, so L is in P.
The above has proved that , since , so P = NP. 4.
Let , i>=3. Suppose i is even. IF i is odd, a similar argument will prove. So there is a polynomial-time Turing machine M such that
Define L2 as follows. From
and Σ2P = Π2P, so L2∈ Π2P, polynomial such that.
so there is some machine M2 running in time
Because
So . So we prove that
, thus decrease 1 quantifier,
, because
,
so , for i>=3,
thus by induction for every i ≥ 3, ΣiP = Σ2P.