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.

    Wednesday, August 30, 2017

    Day 5

    Finished proof of Cook's theorem. Talked about potential NP-incomplete problems such as Graph Isomorphism, recently shown in quasipolynomial time by Laszlo Babai.

    Monday, August 28, 2017

    Friday, August 25, 2017

    Day 3

    Reducibility and NP-Completeness


    Wednesday, August 23, 2017

    Day 2

    More introduction to computation, Turing Machines and time complexity. Defined P and briefly NP.

    Papers mentioned:
    Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem
    Where he defines the Turing machine. Section 9 is worth reading where he basically defends his thesis that this model defines computability.
    Juris Hartmanis and Richard Stearns, On the Computational Complexity of Algorithms
    This paper started the field of computational complexity. It's major insight was to consider resources like time and memory as a function of the input size.
    Jack Edmonds, Paths, Trees and Flowers
    This paper gives a polynomial-time algorithm for graph matching and argues that polynomial-time is a reasonable stand in for efficient computation.
    Alan Cobham, The Intrinsic Computational Difficulty of Functions
    Cobham gave a similar argument for polynomial time.

    Monday, August 21, 2017

    Day 1

    Guest lecture by Venkat.

    Covered basics of Turing Machines, Complexity Classes and Polynomial Time.

    Reminder that Assignment 0 is due Friday. Download and submit on T-Square.

    Assignment 0

    A short assignment is posted on T-Square and due on Friday.

    Friday, June 9, 2017

    Course Overview

    CS 6520 Computational Complexity
    Fall 2017

    Instructor: Lance Fortnow

    Time: MWF 9:05-9:55
    Room: Whitaker Biomedical Engineering 1103

    Description: This course will give an overview of advanced topics in computational complexity including the P versus NP problem, the structure of NP, the polynomial-time hierarchy, circuit complexity, randomness, counting, interactive and probabilistically checkable proofs.

    Detailed list of topics

    Prerequisites: A strong mathematical background and a basic knowledge of Turing machines and the P v NP problem at the level of CS 4510. This is a course meant for advanced students with a strong interest in theoretical computer science--if you just want to fulfill the graduate theory requirement you should take CS 6505.

    Textbook: None. Computational Complexity by Arora and Barak cover much of the material from the course but we won't be following them.

    Coursework: Assignments roughly every other week. This is a theoretical course and assignments will be problem solving and will not involve any programming. There are no exams.

    Course Website: