\documentstyle{article}
\newtheorem{example}{Example}
% \P and \time are already used by LaTeX.  :-(
\newcommand{\ti}{\hbox{TIME}}
\newcommand{\p}{\hbox{P}}
\newcommand{\np}{\hbox{NP}}
\newcommand{\conp}{\hbox{coNP}}
\newcommand{\exptime}{\hbox{EXPTIME}}
\newcommand{\ntime}{\hbox{NTIME}}
\begin{document}
\input{preamble.tex}
\lecture{1}{February 4, 1997}{Daniel A. Spielman}{Henry Cohn}

\section{Time Complexity Classes}

Define
\begin{eqnarray*}
\ti(t(n)) = \{\hbox{languages } L :  L \hbox{ is accepted by a Turing
machine that halts}\\ 
 \hbox{within } t(n) \hbox{ steps}\}.
\end{eqnarray*}
% I couldn't get it to break the displayed equation without doing
% this. 
We won't specify the sort of Turing machine (e.g., one or two tape, or
even a RAM or Kolmogorov machine).  As long as we are consistent, it
won't matter.  Different definitions can change times by a polynomial
factor, but that does not change the definitions of classes like $\p$
and $\np$.

Define
$$
\p = \bigcup_{k \ge 0} \ti(n^k).
$$
Of course, the ``P'' stands for ``polynomial time''.
We'll treat $\p$ as the class of things that can be computed
reasonably/efficiently.  
Define
$$
\exptime = \bigcup_{k \ge 0} \ti(2^{n^k}).
$$
Obviously $\p \subset \exptime$.  One of the few facts we'll prove in
this course is that $\p \ne \exptime$.  Most of the other statements
we deal with will depend on unproved hypotheses.  For example, we
might prove that $\p \ne \np$ implies that a certain problem is hard,
but we generally won't be able to prove it unconditionally.

We can in fact prove the following theorem, which is much stronger
than $\p \ne \exptime$.

\begin{theorem}[Time Hierarchy Theorem]
If $f(n) = o(g(n)/\log g(n))$, then 
$$
\ti(f(n)) \ne \ti(g(n)).
$$
\end{theorem}

This theorem was proved in a prerequisite class.  The proof is an
application of diagonalization.
% The proof wasn't given in detail in class.  Should I insert more
% details? 

Define
\begin{eqnarray*}
\ntime(t(n)) = \{L : L \hbox{ is accepted by a non-deterministic Turing
machine}\\
\hbox{that always halts within } t(n) \hbox{ steps}\}.
\end{eqnarray*}
Recall that a non-deterministic Turing machine has non-deterministic
states, where it can branch.  To see whether the machine accepts,
follow all the branches and see whether any one of them accepts.
Non-deterministic polynomial time is defined by
$$
\np = \bigcup_{k \ge 0} \ntime(n^k).
$$

The fundamental questions we'd like to answer is whether $\p = \np$.
Unfortunately, we've got no idea how to answer it.

One useful way to think of languages in $\np$ is as follows.  A
language $L$ is in $\np$ iff one can verify membership efficiently via
short witnesses.  More formally, that means that there is a language
$L' \in \p$ and a polynomial $p(n)$ such that $x \in L$ iff there
exists $w$ such that $(x,w) \in L'$ and $|w| \le p(|x|)$.  Such a
string $w$ is called a witness.  

\section{Reductions, Completeness, and Hardness}

A language $A$ is {\sl polynomial-time reducible} to a language $B$ if
there is a polynomial-time computable function $f$ such that $x \in A$
iff $f(x) \in B$.  We write $A \le_P B$ in that case.  The idea is
that this condition implies that testing membership in $A$ is no
harder than testing membership in $B$.  (This sort of reduction is
also called mapping reduction, or Karp reduction.)

A language $L$ is called {\sl $\np$-complete} if $L \in \np$ and for
all $A \in \np$, $A \le_P L$.  If any $\np$-complete problem is in
$\p$, then $\p = \np$.  Examples of $\np$-complete languages include
circuit satisfiability (given a Boolean circuit with one output, can
it be made $1$?), SAT, and 3SAT.

Define
$$
\conp = \{L : \bar{L} \in \np\}.
$$
Here $\bar{L}$ is the complement of $L$.
We do not think that $\np=\conp$.

The notion of reduction defined above is too limited for some
situations.  Turing reduction is a more general form of reduction,
defined as follows.  The language $A$ is {\sl polynomial-time Turing
reducible} to $B$ if there is a polynomial-time oracle Turing machine
$M$ that accepts $A$ while using $B$ as an oracle.  We write $A \le_T
B$ in this case.

What this definition means is that the Turing machine can call a
subroutine to ask whether strings are in $B$.  More precisely, an
{\sl oracle Turing machine} has a special tape on which it can write
queries, which are then answered in one step.  (We call it an oracle
because the oracle is allowed to give answers that could not have been
computed efficiently, or even at all.)

A language $L$ is defined to be {\sl $\np$-hard} if $A le_T L$ for all
$A \in \np$ (or, equivalently, for any one $\np$-complete language
$A$).  We can use a slight modification of this definition to talk
about a function being $\np$-hard.

Notice that Turing reduction gives a perfectly good notion of hardness
(in the sense that $\p=\np$ if any $\np$-hard language is in $\p$),
but it is not the same notion one gets from mapping reduction.  For
example, every $\conp$-complete language is $\np$-hard.

\section{Implicit Circuit Value Problem}

Since we know that $\exptime \ne \p$, to find a difficult problem we
just need to find an $\exptime$-complete problem.  A classic example
is the {\sl implicit circuit value problem}.  The {\sl circuit value
problem} is to compute $C(x)$ where $C$ is a given circuit and $x$ an
input; it can clearly be solved in polynomial time.  The implicit
circuit value problem is the same, except that $C$ and $x$ are defined
only implicitly.  Instead of being given $C$ and $x$ directly, one is
given circuits $D$ and $Y$ that describe them as follows.  Given input
$i$, $D$ outputs which gates in $C$ are inputs to gate $i$ and what
type of gate it is.  Given input $i$, $Y$ outputs the $i$-th bit of
$x$.  Thus, $D$ and $Y$ implicitly describe an exponentially-large
circuit $C$ and its input $x$.  Given exponential time, one can
explicitly construct $C$ and $x$ and evaluate $C(x)$, so this problem
is in $\exptime$.  However, no better method comes to mind.  In fact,
one can imitate the proof of Cook's theorem to show that this problem
is $\exptime$-complete.  (Construct a huge tableau of the work tapes
in an accepting computation, and make a circuit that accepts iff the
computation is valid.  The circuit will be immense, but it has a short
implicit description.)

So now we have a problem that cannot be solved efficiently.  However,
it is striking that we do not even know whether $\p/\hbox{poly}$
contains $\exptime$.  (Here, $\p/\hbox{poly}$ is languages recognized
by polynomial-sized circuits, where we can use a different circuit for
each input size.  Clearly, $\p/\hbox{poly}$ properly contains $\p$,
but nobody knows just how large it is.)

\section{The Polynomial Hierarchy}

Some of the most important complexity classes we will deal with are
those in the Polynomial Hierarchy.  If $B$ is a language, define
\begin{eqnarray*}
\np^B = \{\hbox{languages } L \hbox{ such that there is a
non-deterministic polynomial-time}\\
\hbox{ oracle Turing machine with oracle } B
\hbox{ that accepts } L\}.
\end{eqnarray*}
We write $\np^{\np}$ for $\np^B$ where $B$ is $\np$-complete.
Clearly, $\np^{\np}=\np^{\conp}$.  However, $\conp^{\np}$ is
conjecturally different from $\np^{\np}$.  It contains the minimum
circuit problem (given a circuit, is there a smaller one computing the
same function?).  To see that it is in $\conp^{\np}$, notice that one
can guess a smaller circuit and then accept iff there is always an
input on which it differs from the original circuit (ask an $\np$
oracle that question).

Let $\Sigma_1^P = \np$ and $\Pi_1^P = \conp$.  Then continue by
defining 
$$
\Sigma_{i+1}^P = \np^{\Sigma_i^P}
$$ 
and 
$$
\Pi_{i+1}^P = \hbox{co-}\Sigma_{i+1}^P = \conp^{\Sigma_i^P}.
$$
These complexity classes form the Polynomial Hierarchy (PH).  It is 
conjectured that they are all different.
\end{document}