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.

## Wednesday, September 20, 2017

## 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

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.

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}

## 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

Definitions:

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

## 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)) ⊆ ∪

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

^{2}(n)).
Links:

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

## 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 Σ

We say a set S is dense if for some ε>0, |S∩Σ

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.

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

## 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:Σ

We define A to be paddable if there is a function h:Σ

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

^{*}→Σ^{*}- f is computable in polynomial time
- The inverse of f is computable in polynomial time
- f reduces A to B (x in A iff f(x) in B)
- f is 1-1
- f is onto

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

^{*}→Σ^{*}- f is computable in polynomial time
- The inverse of f is computable in polynomial time
- f is 1-1
- f is length-increasing, i.e., |f(x)| > |x| for all strings x.

^{*}×Σ^{*}→Σ^{*}- h is computable in polynomial time
- For all x,y, x is in A iff h(x,y) is in A
- For all y, |h(x,y)| > |y|
- For all x, y and y' with y≠y', h(x,y)≠h(x,y')
- There is a polynomial-time computable function g s.t. for all x,y, g(h(x,y))=y

- Every A in NP reduces to Satisfiability via a 1-1 length-increasing reduction.
- If B reduces to a paddable set A then there is a reduction from B to A that is length-increasing and invertible.
- 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.

Subscribe to:
Posts (Atom)