CPSC 506, Sept 10, 2012, Joel Friedman

Here are some brief notes on what we will do next week.

On Sept 5  we described Turning machines and related models, claiming
that a poly time algorithm on any model would imply a poly time
algorithm on the others.

Sept 10 and 12 we will do the following (one can always hope):

We will describe the classes DTIME(f(n)), DSPACE(f(n)),
and explain that DTIME(f(n)) <= DSPACE(f(n)) <= Union_c DTIME( c^(f(n)) )
so LOG-SPACE <= P, etc.

We will review non-deterministic Turing Machines, defining NTIME and NSPACE,
and then explain why NP is the same as the definition in my notes and the
text.  Then we will define the polynomial time hierarchy, and explain its
relation to P, NP, and why it was introduced.

We shall then explain roughly how a universal TM can simulate n steps of any
TM computation in time c n log(n), and show separation results such as
DTIME( n^a ) < (strictly less than)  DTIME ( n^a  log^2(n) )  for any
constant a.

At this point or before, I will state facts that you are assumed to have
seen in an earlier course (or are willing to read up on): Reductions,
NP-completeness, Cook-Levin, and uncomputable problems; this last topic
is very similar to the topic in the previous paragraph (i.e., diagonalization).
We will discuss oracle Turing machines and how they suggest a different
(sometimes better) notion of "reduction."  These theorems are not strictly
necessary for this course, but will explain the interest in P versus NP
and give you some idea of the basics of Turing machine computation.

This will probably take us one week.  After that we may briefly discuss
the "Gap Theorem" and other curious results. We will definitely describe
some details regarding the B-G-S theorem and why not to attack P vs. NP
with diagonalization alone.