CS 3800 2016-11-21. Return this single, two-sided sheet. Your name:
1. Show that there is a polynomial-time reduction from 3SAT to SYSTEM, defined as follows. A linear inequality is an inequality involving sums of variables and constants, such as x+y ≥ z, x ≤ −17, and so on. A system of linear inequalities has an integer solution if it is possible to substitute integer values for the variables so that every inequality in the system becomes true. The language SYSTEM consists of systems of linear inequalities that have an integer solution. For example,
(x + y ≥ z, x ≤ 5, y ≤ 1, z ≥ 5) ∈ SYSTEM (x + y ≥ 2z, x ≤ 5, y ≤ 1, z ≥ 5) ̸∈ SYSTEM
2. Without using the Cook-Levin theorem, prove that the following language is NP-complete:
L = {(M,x,1t) : M is a Turing machine : ∃y ∈ {0,1}t : M(x,y) accepts within t time steps}.
3. Show that NTIME(n2) ⊆ P ⇒ P = NP. Hint: use padding. 4. Show that if Σ2P = Π2P then for every i ≥ 3,ΣiP = Σ2P.