\documentclass[10pt]{article}
\usepackage{fullpage}
\input{preamble.tex}
\usepackage{amsmath}

%\usepackage{epsfig}

\begin{document}

\newcommand{\lang}{\mathit}
\newcommand{\cclass}{\mathrm}
\newcommand{\TIME}{\cclass{TIME}}
\newcommand{\SPACE}{\cclass{SPACE}}
\newcommand{\NTIME}{\cclass{NTIME}}
\newcommand{\NSPACE}{\cclass{NSPACE}}
\newcommand{\ATIME}{\cclass{ATIME}}
\newcommand{\ASPACE}{\cclass{ASPACE}}

\lecture{8}{Mar 5, 2007}{Madhu Sudan}{Hooyoung Chung}

\section{Overview}
\begin{itemize}
\item Alternation
\item Fortnow's Theorem: \emph{$\lang{SAT}\notin\cclass L$ or $\lang{SAT}\notin\bigcap_{\varepsilon>0}\TIME(n^{1+\varepsilon})$}
\end{itemize}

\section{Aside: Definition of $\TIME(t(n))$}

Consider $\lang{PALINDROME}=\{x\cdot x^{\cal R}\mid x\in\Sigma^*\}$.
Is $\lang{PALINDROME}\in\TIME(O(n))$?
If we can use two tapes, the answer is clearly \emph{yes}.
On the other hand, if our measure of time complexity involves one-tape TMs, then it can be shown that $\lang{PALINDROME}$ requires $\Omega(n^2)$.
This bound conflicts with our intuition, which says that $\lang{PALINDROME}$ is a simple problem with an obvious linear time solution.
We conclude that one-tape TMs are a poor model of computation where time is concerned.

How about two-tape TMs? It can be shown that, potentially at the cost of extra space, a two-tape TM can simulate the computation of a generic multitape TM with only logarithmic slowdown. As a matter of convention, $\TIME(t(n))$ will generally denote the class of problems decidable by machines with any constant number of tapes in time $\le t(n))$.

\paragraph{An ``extra credit exercise.''}

Build a universal one-tape TM $U$ that, on input $\langle M,x\rangle$, simulates $M$ on $x$ with sublogarithmic slowdown, where $M$ is a one-tape TM; that is, if $M$ runs in $t(n)$, $U$ should output $M(x)$ in $o(t(n)\lg t(n))$.

\section{The Alternating TM}

The alternating TM is a generalization of the nondeterministic Turing machine, in that it is allowed to perform many ``threads'' of computation simultaneously.
We augment the deterministic TM model with two special kinds of states: an \emph{existential} ($\exists$) and a \emph{universal} ($\forall$), which are allowed to transition to two other states at once.
We introduce the concept of states accepting or rejecting, where this behavior is governed by the type of state.
$\exists$ states accept when at least one outgoing transition accepts; $\forall$ states accept when both outgoing transitions accept.
A normal state has exactly one outgoing transition, and accepts when that transition accepts.
The alternating TM accepts when its start state accepts.

The computation of an alternating TM $M$ on an input $w$ is naturally represented as a \emph{computation tree}, whose nodes are the configurations $M$ enters when it is run on $w$. A configuration incorporates the tape contents, head position, and finite state of $M$. The tree is rooted at the start configuration, and we draw an edge from configuration $a$ down to $b$ if a transition takes $a$ to $b$.

When we discuss alternating TMs, we are interested in these resources:
\begin{itemize}
\item \emph{Time}, measured as the depth of the computation tree. If an alternating TM $M$ has computation tree depth $\le t(n)$ on all inputs of size $n$, then $L(M)\in\ATIME(t(n))$. 
\item \emph{Space}, the maximum space used in any configuration in the computation tree. If an alternating TM $M$ terminates on all inputs of size $n$ and uses space $\le s(n)$ along any path, then $L(M)\in\ASPACE(s(n))$.
\item \emph{Alternation} counts the maximum number of times the machine alternates between existential and universal states and vice versa, along any path in the computation tree (normal states are not considered). For instance, any deterministic TM is an alternating TM with zero alternations. 
\end{itemize}

\subsection*{Motivation for studying alternation}

Why study alternation?

\begin{enumerate}
\item It models interesting problems; for instance, the set of problems decidable in polynomial time using only existential states is exactly $\cclass{NP}$, problems decidable in polynomial time using only universal states $=\cclass{coNP}$.
An example of a problem which (we think) requires $\exists$ followed by $\forall$ is formula minimization, i.e.,
\[\{(\phi,k)\mid\exists\psi\colon|\psi|\le k\text{ and }\forall x\colon\phi(x)=\psi(x)\}\] 
\item It offers useful perspective for the comparison of time and space, as shown by the containments:
\begin{eqnarray*}
&\NSPACE(s(n))\subseteq\ATIME((s(n))^2)\subseteq\SPACE((s(n))^2)\\
&\TIME(2^{s(n)})\subseteq\ASPACE(s(n))\subseteq\TIME(2^{O(s(n))})
\end{eqnarray*}
\end{enumerate}

\section{Fortnow's Theorem}

Fortnow's theorem states that $\lang{SAT}\notin\cclass L$ or $\lang{SAT}\notin\TIME(n^{1+\varepsilon})$ for some $\varepsilon>0$.
We believe $\cclass P\ne\cclass{NP}$, which implies both of these trivially, but have not been able to prove it.

The conventional statement of Cook's theorem is that all nondeterministic-polynomial-time-computable languages have a polynomial time reduction to $\lang{SAT}$. In our proof, we will use the following stronger version, which gives useful upper bounds on the running time and space of the (optimal) reduction.

\begin{theorem}
\label{cook}
\emph{(Cook)}
Given an increasing function $t(n)$, there is a $c$ such that for any nondeterministic TM $M$ mapping reduction from $L(M)$ to $\lang{SAT}$ running in time $t(n)$, there is a mapping reduction $f_M$ from $L(M)$ to $\lang{SAT}$ which is computable in time $O(t(n)\lg t(n))$ and space $c\lg t(n)$ and yields a formula of size $O(t(n)\lg t(n))$.
\end{theorem}
(For a proof, see S. Cook, Short propositional formulae represent non-deterministic computation, {\em Information Processing Letters}, 26:269-270, 1988.)

The heart of the proof of Fortnow's theorem is in the following lemmas.

\begin{claim}
\label{Limp}
$\lang{SAT}\in\cclass L\implies\NTIME(t(n))\subseteq\SPACE(c\lg t(n))$ for some constant $c$.
(The idea: if $\lang{SAT}\in\cclass L$, ``all computation is small space.'')
\end{claim}
\begin{proof}
From theorem \ref{cook}, we can reduce any problem in $\NTIME(t(n))$ to $\lang{SAT}$ using space within some factor of $\lg n$. If $\lang{SAT}\in\cclass L$, then $\lang{SAT}\in\SPACE(c_0\lg t(n))$ for some $c_0$, so we can solve any problem in $\NTIME(t(n))$ in space $c\lg t(n)$ for some $c$.
\end{proof}

\begin{claim}
\label{T1Eimp}
For any $\varepsilon>0$, $\lang{SAT}\in\TIME(n^{1+\varepsilon})\implies\ATIME(a,a\cdot t(n)^{c/a})\subseteq\ATIME(a-1,a\cdot t(n)^{(c/a)(1+\varepsilon)})$.
(If $\lang{SAT}\in\TIME(n^{1+\varepsilon})$, ``alternation is not powerful.'')
\end{claim}

\begin{claim}
\label{altsav}
$\SPACE(s(n))\subseteq\ATIME(a,a\cdot2^{s(n)/a})$.
(``Alternation is powerful (for small space computation).'')
\end{claim}
\begin{proof-idea}
Proof similar to the standard proof of Savitch's theorem. Given a deterministic TM $M$ running in time $t(n)$, we can find out if it accepts a string by looking for a path of length $t(n)$ between its start and accepting configuration on that string. The way to do this is to guess the configuration in the middle and recursively check if paths of length $t(n)/2$ exist from the start to the midpoint and from the midpoint to the end. A deterministic TM which uses space $s(n)$ uses time $2^{s(n)}$.
\end{proof-idea}

\paragraph{Notation for alternating time.}
Note the use of $\ATIME(a,t(n))$; this denotes the classs of languages decidable in $t(n)$ by alternating TM that make a constant $\le a$ alternations, e.g., $\ATIME(0,t(n))=\TIME(t(n))$. (Previously we defined $\ATIME(t(n))$, the class of languages decidable in time $t(n)$ for some alternating TM using an unrestricted amount of alternation.)

\begin{theorem}
\label{fortnow}
\emph{(Fortnow)}
For any $c<\infty$, we can find $\varepsilon>0$ such that
\[\lang{SAT}\in\SPACE(c\lg n)\implies \lang{SAT}\notin\TIME(n^{1+\varepsilon}).\]
\end{theorem}
(This statement of Fortnow's theorem is equivalent to the one in the overview.)

\begin{proof}
Assume that $\lang{SAT}\in\cclass L\cup\TIME(n^{1+\varepsilon})$.
\begin{alignat*}{2}
\TIME(t(n))&\subseteq\NTIME(t(n))&\qquad\qquad\\
&\subseteq\SPACE(c\lg t(n))&&\text{by Claim \ref{Limp}}\\
&\subseteq\ATIME(a,a\cdot t(n)^{c/a})&&\text{by Claim \ref{altsav}}\\
&\subseteq\ATIME(a-1,a\cdot t(n)^{(c/a)(1+\varepsilon)})&&\text{by Claim \ref{T1Eimp}}\\
&\subseteq\ATIME(a-2,a\cdot t(n)^{(c/a)(1+\varepsilon)^2})&&\text{likewise}\\
&\qquad\qquad\qquad\vdots\\
&\subseteq\ATIME(0,a\cdot t(n)^{(c/a)(1+\varepsilon)^a})\\
&=\TIME(a\cdot t(n)^{(c/a)(1+\varepsilon)^a})
\end{alignat*}
which can only be true if $\frac{2c}{a}(1+\varepsilon)^a\ge1$.
\end{proof}

\end{document}