Friday, September 29, 2017

Day 16

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

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


Wednesday, September 27, 2017

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.

Monday, September 25, 2017

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.


  • 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. 

Friday, September 22, 2017

Day 13

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

Wednesday, September 20, 2017

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.

Monday, September 18, 2017

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
  • PA = NPA
  • PB ≠ NPB
  • 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
  • Friday, September 15, 2017

    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


    • 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.

    Wednesday, September 13, 2017

    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(cf(n))

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


    Friday, September 8, 2017

    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 Σn 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| ≥ 2nε for all n. A set S is sparse if for some c, |S∩Σn|≤ nc. 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.

    Wednesday, September 6, 2017

    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.

    Friday, September 1, 2017

    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.