Day 16

Karp-Lipton result that if SAT has a polynomial-size circuit family then PH = Σ^p₂.

Definitions of circuit complexity classes (NCⁱ, ACⁱ). NCⁱ is the set of languages accepted by poly-size O(logⁱ n) depth with bounded fan-in. ACⁱ circuits are the same with no restriction on fan-in.

Links:

• Some connections between nonuniform and uniform complexity classes by Richard Karp and Richard Lipton. 
• Wikipedia article on Karp-Lipton with proof. 
• Wikipedia article on NC

Day 15

Assignment 2 now available on the T-Square site. Due October 11.

Defined circuits, size and depth. Showed that a language has a polynomial-size circuit family if and only if L is in P/poly.

Blog post on P/poly.

Day 14

Defined quantified Boolean formula and showed that TQBF, the set of true quantified Boolean formula, is PSPACE-complete.

Assignment 1 has been graded. Average score is 62. Solutions are posted to the resources section of the T-Square site. Assignment 2 will be handed out Wednesday.

Links:

• Alternation by Chandra, Kozen and Stockmeyer. This is the paper that showed the equivalence of alternating polynomial time and PSPACE and my other relationships.
• Nice write-up of proof that TQBF is PSPACE-complete via Joan Feigenbaum. 

Day 13

We talked about the three definitions of the polynomial-time hierarchy, by oracles, alternation and quantification, and the basic properties.

• The equivalence problem for regular expressions with squaring requires exponential space by Albert Meyer and Larry Stockmeyer. This is the paper that first defined the polynomial-time hierarchy. 
• The wikipedia article on the polynomial-time hierarchy goes through all three definitions and the basic relationships.
• Completeness in the Polynomial-Time Hierarchy by Marcus Schaefer and Chris Umans. A compendium of problems complete for various higher levels of the hierarchy. 

Day 12

Guest lecture from Venkat.

Defined polynomial-time hierarchy in terns of oracle TMs and stated some simple facts about the hierarchy. Defined alternating Turing machines. Started the proof of the characterization of polynomial-time hierarchy using alternating Turing machines.

Details and links will come in next post.

Day 11

Finished proof of Immerman-Szelepcsényi. Links in last post.

Defined oracle Turing machines and the Baker-Gill-Solovay result that there exist oracles A and B such that

• P^A = NP^A
• P^B ≠ NP^B

Links:

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

You can simply take A to be any PSPACE-complete problem. For B, here is a good write-up. 

Day 10

Today we covered the complements of languages and co-classes and did most of the proof of the Immerman-Szelepcsényi theorem that non-deterministic space is closed under complement. In particular we focused on the proof that NL = co-NL

Definitions:

• The complement of a language L, denoted L, is the set of strings not in L.
• For a complexity class C, we define co-C as the set of languages L for L in C.

Links:

• My writeup of Immerman-Szelepcsényi
• Nondeterministic Space is Closed under Complementation by Neil Immerman
• The method of forced enumeration for nondeterministic automata by Róbert Szelepcsényi

Day 9

We looked at deterministic and nondeterministic space complexity and showed the basic relationships:

DTIME(f(n)) ⊆ NTIME(f(n)) ⊆ DSPACE(f(n)) ⊆ NSPACE(f(n)) ⊆ ∪_c DTIME(c^f(n))

We also proved Savitch's theorem that NSPACE(s(n)) is contained in DSPACE(s²(n)).

Links:

• Relationships between nondeterministic and deterministic tape complexities by Walter Savitch
• My writeups of Space Complexity and Savitch's Theorem

Day 8

Assignment 1, due Monday, September 18, has been posted on T-Square. I highly recommend you start thinking about the problems immediately.

The Berman-Hartmanis Isomorphism Conjecture states that all NP-complete sets are polynomial-time isomorphic to each other. The conjecture is still open.

Let Σⁿ be the set of all strings of length n and Σ^≤n be the set of all strings of length at most n.

We say a set S is dense if for some ε>0, |S∩Σ^≤n| ≥ 2^nε for all n. A set S is sparse if for some c, |S∩Σⁿ|≤ n^c. Every finite set is sparse and no dense set is sparse.

We showed in class that if the Berman-Hartmanis conjecture is true then every NP-complete set is dense. In paticular under this assumption there are no sparse or finite NP-complete sets and P ≠ NP.

The Berman-Hartmanis conjecture remains open but Mahaney proved the following: If there is a sparse NP-complete set then P = NP. In class we gave the proof of Ogihara and Watanabe which I also wrote up in my blog.

Day 7

The Cantor-Bernstein Theorem states that for any two arbitrary sets A and B if there are 1-1 functions from A to B and B to A then there is a 1-1 and onto function from A to B. How does this carry into complexity?

Two sets of strings A and B are polynomial-time isomorphic if there is a function f:Σ^*→Σ^*

1. f is computable in polynomial time
2. The inverse of f is computable in polynomial time
3. f reduces A to B (x in A iff f(x) in B)
4. f is 1-1
5. f is onto

We say f is a length-increasing invertible reduction if there is a f:Σ^*→Σ^*

1. f is computable in polynomial time
2. The inverse of f is computable in polynomial time
3. f is 1-1
4. f is length-increasing, i.e., |f(x)| > |x| for all strings x.

We define A to be paddable if there is a function h:Σ^*×Σ^*→Σ^*

1. h is computable in polynomial time
2. For all x,y, x is in A iff h(x,y) is in A
3. For all y, |h(x,y)| > |y|
4. For all x, y and y' with y≠y', h(x,y)≠h(x,y')
5. There is a polynomial-time computable function g s.t. for all x,y, g(h(x,y))=y

We showed (see Berman-Hartmanis) that

1. Every A in NP reduces to Satisfiability via a 1-1 length-increasing reduction.
2. If B reduces to a paddable set A then there is a reduction from B to A that is length-increasing and invertible. 
3. If A and B reduce to each other via length-increasing invertible reductions then they are isomorphic.

Essentially all the commonly known NP-complete problems are paddable and thus isomorphic to Satisfiability and each other.

Day 6

We proved Ladner's Theorem that there exists a set A such that A is in NP, A is not in P and A is not NP-complete. Here is a write-up.

Enjoy the Labor Day weekend and see you on Wednesday.