Lecture 7

The Polynomial-Time Hierarchy

Lecture 6

Alternation

True Quantified Boolean Formulas (TQBF sometimes written QBF) is PSPACE-Complete (Proof)
Similar to the proof of Savitch's Theorem

Introduced Alternating Turing Machines
All based on paper Alternation by Chandra, Kozen and Stockmeyer

HW1 is now posted, due Friday September 4 at 5 PM on T-Square

Ground Rules for assignments
You can work together but should write up solutions in your own words
Best to solve the problems without outside help but if you do look up the solution please cite the source and write up the solution in your own words

Lecture 5

There exists oracle A and B such that P^A = NP^A and P^B ≠ NP^B

Relativizations of the P =? NP Question by Baker, Gill and Solovay

Homework 1 will be posted Friday

Lecture 4

Mahaney's Theorem: There are no sparse NP-complete sets unless P = NP

Introduced oracle Turing machines. Next class: Baker-Gill-Solovay

Lecture 3

Ladner's Theorem that, assuming P is different than NP, there is a language L in NP, L not in P and L not NP-complete.

Two Proofs of Ladner's Theorem by Lance Fortnow

Lecture 2

Assignment 0 is posted and should be submitted via T-Square. Due by August 20 at 5 PM. If you are not registered and want access to the T-Square site please contact the instructor.

NP-completeness and Cook's Theorem.

A is reducible to B if there is a polynomial-time function f such that

• x in A implies f(x) in B
• x not in A implies f(x) not in B

L is NP-complete if

1. L is in NP, and
2. For all A in NP, A is reducible to L

We will show that CNF-SAT is NP-complete. Let A be a language in NP accepted by a nondeterministic Turing machine M. Fix an input x. We will create a 3CNF formula φ that will be satisfiable if and only if there is a proper tableau for M and x.

Let m be the running time of M on x. m is bounded by a polynomial in |x| since A is in NP. m is also a bound on the size of the configurations of M(x).

We will create a set of Boolean variables to describe a tableau and a set of clauses that will all be true if and only if the tableau is proper. The variables are as follows.

• qij: true if confi is in state j.
• hik: true if the head in confi is at location k.
• tikr: true if the tape cell in location k of confi has element r.

We create four clause groups to check that the tableau is proper.

1. Every configuration has exactly one state, head location and each tape cell has one element.
2. conf0 is the initial configuration.
3. confm is accepting.
4. For each i≤m, confi+1 follows from confi in one step.

1. We will just do this for states. The others are similar. Suppose we have u possible states. 

Each configuration in at least one state. For each i we have

qi0 OR qi1 OR ... OR qiu

Each configuration in at most one state. For each i and possible states v and w, v≠w

(NOT qiv) OR (NOT qiw)

2. Let x=x1...xn, b the blank character and state 0 the initial state. We have the following single variable clauses,

q00

h01

t0ixi for i≤n

t0ib for i>n

3. Let a be the accept state. We need only one single variable clause.

qma

4. We need two parts. First if the head is not over a tape location then it should not change.

((NOT hik) AND tikr)→ ti(k+1)r

Now this doesn't look like an OR of literals. We now apply the facts that P→Q is the same as (NOT P) OR Q and NOT(R AND S) is equivalent to (NOT R) OR (NOT S) to get

hik OR (NOT tikr) OR t(i+1)kr

At this point none of the formula has been dependent on the machine M. Our last set of clauses will take care of this. Recall the program of a Turing machine is a mapping from current state and tape character under the head to a new state, a possibly new character under the head and a movement of the tape head one space right or left. A nondeterministic machine may allow for several of these possibilities. We add clauses to prevent the wrong operations.

Suppose that the following is NOT a legitimate transition of M: In state j and tape symbol r, will write s, move left and go to state v. We prevent this possibility with the following set of clauses (for all appropriate i and k).

(qij AND hik AND tikr)→ NOT(t(i+1)ks AND hi(k-1) AND q(i+1)v)

which is equivalent to

(NOT qij) OR (NOT hik) OR (NOT tikr) OR (NOT t(i+1)ks) OR (NOT hi(k-1)) OR (NOT q(i+1)v)

We do this for every possible illegitimate transition. Finally we just need to make sure the head must go one square right or left in each turn.

(NOT hik) OR h(i+1)(k-1) OR h(i+1)(k+1)

Just to note in the above formula we need special care to handle the boundary conditions (where k is 1 or m) but this is straightforward.

Lecture 1

Overview of the course. Definitions of Turing machine, deterministic and nondeterministic time and space complexity.

Turing Machine

Finite control: set of states

Move: scan symbol, write symbol, move left or right, change state

M = (Q,Σ,Γ,δ,q0,B,qacc,qrej)

Q finite set of states

Σ finite alphabet B is not in Σ

Γ finite tape alphabet: Σ is a strict subset of Γ (no B)

q0 - initial state

qacc,qrej halting states: accept and reject

δ maps Q×Γ→Q×Γ×{L,R}