%\documentstyle[10pt,twoside]{article}
\documentstyle[twoside]{article}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}

%
% The following commands sets up the lecnum (lecture number)
% counter and make various numbering schemes work relative
% to the lecture number.
%
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}

%
% The following macro is used to generate the header.
%
\newcommand{\lecture}[4]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{lecnum}{#1}
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf CSC2401~Introduction to Computational Complexity
                        \hfill Fall 1998} }
       \vspace{4mm}
       \hbox to 6.28in { {\Large \hfill Lecture #1: #2  \hfill} }
       \vspace{2mm}
       \hbox to 6.28in { {\it Lecturer: #3 \hfill Scribe: #4} }
      \vspace{2mm}}
   }
   \end{center}
   \markboth{Lecture #1: #2}{Lecture #1: #2}
   \vspace*{4mm}
}

%
% Convention for citations is authors' initials followed by the year.
% For example, to cite a paper by Leighton and Maggs you would type
% \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}.
% (To avoid bibliography problems, for now we redefine the \cite command.)
%
\renewcommand{\cite}[1]{[#1]}

\input{epsf}

%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{FIGURE-SIZE}{CAPTION}{FILENAME}
\newcommand{\fig}[4]{
			\vspace{0.2 in}
			\setlength{\epsfxsize}{#2}
			\centerline{\epsfbox{#4}}
			\begin{center}
			Figure \thelecnum.#1:~#3
			\end{center}
	}

% Use these for theorems, lemmas, proofs, etc.
\newtheorem{theorem}{Theorem}[lecnum]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}

% Some useful equation alignment commands, borrowed from TeX
\makeatletter
\def\eqalign#1{\,\vcenter{\openup\jot\m@th
  \ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
      \crcr#1\crcr}}\,}
\def\eqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &$\displaystyle{{}##}$\hfil\tabskip\@centering
    &\llap{$##$}\tabskip\z@skip\crcr
    #1\crcr}}
\def\leqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &$\displaystyle{{}##}$\hfil\tabskip\@centering
    &\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr
    #1\crcr}}
\makeatother

% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM HERE:

\begin{document}
%FILL IN THE RIGHT INFO.
%\lecture{**LECTURE-NUMBER**}{**DATE**}{**LECTURER**}{**SCRIBE**}
\lecture{13}{October 27}{Micah Adler}{MohammadReza Salavatipour}

\section{PSPACE-completeness}
We are going to introduce the PSPACE-Complete class of languages.

\begin{definition}
A language $L$ is PSCAPE-Complete if it satisfies the following two
conditions:
\begin{enumerate}
\item $L\in PSPACE$
\item $\forall \: L'\in PSPACE,  \; L'{\leq}_p L$
\end{enumerate}
\end{definition}

The first problem we show to be PSPACE-Complete is a generalization of SAT
called Quantified Boolean Formula in which we have 
\begin{description}
\item {Universal qualifiers} : $\forall x$ (for all x)
\item {Existential qualifiers} : $\exists x$ (there exists x)
\end{description}

\begin{definition}
A QBF is a boolean formula prefixed by a string of universal and
existential qualifiers, one for each variable in the formula.
Just like the SAT problems, the variables can take {\em True} or {\em
False} values.
\end{definition}
Example: $\forall x\exists y ((x\vee y)\wedge(\overline x\vee \overline
y))$ is a QBF that can be satisfied but
  $\exists y \forall z ((y\vee z)\wedge(\overline y\vee\overline z))$ is
not True.

\begin{definition}
TQBF=\{$\Phi | \Phi$ is a true QBF\}
\end{definition}
In the textbook, this is called QSAT. SAT is a TQBF with only $\exists$
qualifiers and Validity is a TQBF with only $\forall$ qualifiers.

\begin{theorem}
TQBF is PSPACE-Complete.
\end{theorem}
\begin{proof}
First we show that TQBF is in PSPACE. To do so, we give a recursive
algorithm. 

For an input $\Phi$ :
\begin{itemize}
\item if $\Phi=\exists x\Psi$ then recurse on $\Psi$ with both $x=True$
and $x=False$, accept if \underline {either} accept.
\item if $\Phi=\forall x\Psi$ then recurse on $\Psi$ with
both $x=True$ and $x=False$, accept if \underline{both} accept.
\end{itemize}
we show that in both cases we use PSPACE. For both cases we reuse the
cells for recursive calls. The space needed by this algorithm is in
order of the recursion depths which is equal to the number of variables
and so is linear.

For proving the completeness, we show that: $$\forall L\in PSPACE,
L{\leq}_p TQBF.$$
We use an idea like the cook's theorem.

\underline{Idea} : $L$ is decided by a 1-tape T.M, M which uses at most
$n^k$ spaces for a given input of size $n$. For given input $w$, construct
the QBF called ${\Phi}_w$ such that: ${\Phi}_w\in TQBF
\Longleftrightarrow$ M accepts w $\Longleftrightarrow w \in L$

First, we try to use the cook's construction. We had a configuration
tableau. It has $n^k$ columns but the number of rows was $c^{n^k}$ which
is  exponential. Cook's
formula has size $\Theta(l)$ where $l$ is the number of cells in tableau.
To have a polynomial number of rows, we are going to use the Savitch idea.
We are going to consider pathes between two nodes in the configuration
graph with length $l$ and recursively divide the path into two subpathes
of
length $l\over 2$.

\begin{definition}
For configurations $C_a$ and $C_b$, we say that we can go from $C_a$ to
$C_b$ in $t$ steps, $C_a \stackrel{t}{\Longrightarrow} C_b$ if $C_b$
follows from $C_a$ in t steps.  
\end{definition} 

The subproblem we have is as follows: given configurations $C_a$ and
$C_b$, we construct a QBF, ${\Phi}_{C_a \stackrel{t}{\rightarrow}C_b}$ in
polynomial time, where \({\Phi}_{C_a\stackrel{t}{\rightarrow}C_b}=T
\Longleftrightarrow C_a\stackrel{t}{\rightarrow}C_b\).
We are going to use the Savitch recursive idea. We construct the
${\Phi}_{C_a\stackrel{a}{\rightarrow}C_b}$ as follows:

\begin{description}
\item {base case (t=1):} Use Cook's construction.
\item {recursive case (t$>$1):} 
\[\exists
C_{mid}({\Phi}_{C_a\stackrel{t\over 
2}{\rightarrow}C_{mid}}\wedge{\Phi}_{C_{mid}\stackrel{t\over
2}{\rightarrow}C_b})\]
where $\exists C_{mid}$ is: $\exists x_1\exists x_2 \ldots \exists x_r$
where $x_1, x_2, \ldots, x_r$ encode a T.M configuration $C_{mid}$ using
Cook's construction. 
\end{description}

But this one also doesn't lead to a polynomial
construction.
Because for the recursive case we introduce two new
subproblems. Thus for each level of recursion the number of variables
doubles and total number of levels is of $O(n^k)$ which is too large.
So we use the following construction.

{\bf Actual Construction:} We use the universal qualifiers to reduce the
overall formula size. Again, define the
${\Phi}_{C_a\stackrel{t}{\rightarrow}C_b}$ as:
\begin{description}
\item {base case (t=1):} use Cook's construction
\item {recursive case (t$>$1):} 
$$\exists C_{mid} \forall C_d \forall
C_e[((C_d=C_a)\wedge(C_e=C_{mid}))\vee((C_d=C_{mid})\wedge(C_e=C_b))]\Longrightarrow
{\Phi}_{C_d\stackrel{t\over 2}{\rightarrow}C_e}$$
\end{description}
We use $\forall\forall$ for considering all posibilities of $C_d$ and
$C_e$ and each of $C_{mid}=x_1,x_2,\ldots,x_r$, $C_d=y_1, y_2,
\ldots,
y_r$, and $C_e=z_1, z_2, \ldots, z_r$ represent a T.M configuration.

Let ${\Phi}_w={\Phi}_{C_{start}}\stackrel{d^{n^k}}{\rightarrow}C_{accept}$
which $C_{start}$ is the start state and we have the unique accept state
configuration. So ${\Phi}_w$ is polynomial in $|w|$ because level of
recursion is of $O(n^k)$, number of new variables at each level is of
$O(n^k)$ and each variable in final formula is used only a constant number
of times. Thus $|{\Phi}_w|=O(n^{2k})$.
\end{proof}

\section{Finding Optimal Strategies in 2-Person Games}
An example of 2-person game is the Formula Game. It has two players
called {\em $\exists$ player} and {\em $\forall$ player}
 and 
given a QBF, $\Phi$. Players take turns choosing values for variables
of $\Phi$ in order of qualifiers in $\Phi$. If the resulting formula is
true then the $\exists$ player wins, otherwise the $\forall$ player wins.
\begin{theorem}
QBF is True $\Longleftrightarrow$ The $\exists$ player has a winning
strategy in the formula game for $\Phi$.
\end{theorem}

\begin{proof}
The proof is direct from the definition of qualifiers.
\end{proof}

Therefor, the question of weather the $\exists$ player has a winning
strategy is also PSPACE-Complete.

Some other 2-person games are : GO and Chess.
\begin{description}
\item {\underline {GO}} An ancient game with two players on a $n\times n$
board. The problem is determining weather a given GO position has a
winning strategy for player 1. This problem is also PSPACE-Complete. 
\item {\underline {CHESS}} if we consider a $n\times n$ board and we scale
the number of piceses then determining if a given chess position has a 
winning strategy for White is PSPACE-Hard.
\end{description}


% **** YOUR NOTES GO HERE:

% Some general latex examples and examples making use of the
% macros follow.  
%**** IN GENERAL, BE BRIEF. LONG SCRIBE NOTES, NO MATTER HOW WELL WRITTEN,
%**** ARE NEVER READ BY ANYBODY.
%This lecture's notes illustrate some uses of
%various \LaTeX\ macros.  
%Take a look at this and imitate.
%
%\section{Some theorems and stuff} % Don't be this informal in your notes!
%
%We now delve right into the proof.
%
%\begin{lemma}
%This is the first lemma of the lecture.
%\end{lemma}
%
%\begin{proof}
%The proof is by induction on \ldots.
%For fun, we throw in a figure.
%%%%NOTE USAGE !
%\fig{1}{1in}{A Fun Figure}{funfig.eps}
%
%This is the end of the proof, which is marked with a little box.
%\end{proof}
%
%\subsection{A few items of note}
%
%Here is an itemized list:
%\begin{itemize}
%\item this is the first item;
%\item this is the second item.
%\end{itemize}
%
%Here is an enumerated list:
%\begin{enumerate}
%\item this is the first item;
%\item this is the second item.
%\end{enumerate}
%
%Here is an exercise:
%
%{\bf Exercise:}  Show that ${\rm P}\ne{\rm NP}$.
%
%Here is how to define things in the proper mathematical style.
%Let $f_k$ be the $AND-OR$ function, defined by
%
%\[ f_k(x_1, x_2, \ldots, x_{2^k}) = \left\{ \begin{array}{ll}
%
%	x_1 & \mbox{if $k = 0$;} \\
%
%	AND(f_{k-1}(x_1, \ldots, x_{2^{k-1}}),
%	   f_{k-1}(x_{2^{k-1} + 1}, \ldots, x_{2^k}))
%	 & \mbox{if $k$ is even;} \\
%
%	OR(f_{k-1}(x_1, \ldots, x_{2^{k-1}}),
%	   f_{k-1}(x_{2^{k-1} + 1}, \ldots, x_{2^k}))	
%	& \mbox{otherwise.} 
%	\end{array}
%	\right. \]
%
%\begin{theorem}
%This is the first theorem.
%\end{theorem}
%
%\begin{proof}
%This is the proof of the first theorem. We show how to write pseudo-code now.
%%*** USE PSEUDO-CODE ONLY IF IT IS CLEARER THAN AN ENGLISH DESCRIPTION
%
%Consider a comparison between $x$ and~$y$:
%\begin{tabbing}
%\hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \=\kill
%\>{\bf if} $x$ or $y$ or both are in $S$ {\bf then } \\
%\>\> answer accordingly \\
%\>{\bf else} \\
%\>\>    Make the element with the larger score (say $x$) win the comparison \\
%\>\> {\bf if} $F(x) + F(y) < \frac{n}{t-1}$ {\bf then} \\%
%\>\>\> $F(x) \leftarrow F(x) + F(y)$ \\
%\>\>\> $F(y) \leftarrow 0$ \\
%\>\> {\bf else}  \\
%\>\>\> $S \leftarrow S \cup \{ x \} $ \\
%\>\>\> $r \leftarrow r+1$ \\
%\>\> {\bf endif} \\
%\>{\bf endif} 
%\end{tabbing}
%
%This concludes the proof.
%\end{proof}
%
%
%\section{Next topic}
%
%Here is a citation, just for fun \cite{CW87}.
%

% **** THIS ENDS THE EXAMPLES. DON'T DELETE THE FOLLOWING LINE:


% If you need to add references, use the following format:

%\section*{References}
%
%\begin{itemize}
%\item[CW87] {\sc D.~Coppersmith} and {\sc S.~Winograd}, 
%Matrix multiplication via arithmetic progressions,
%{\it Proceedings of the 19th ACM Symposium on Theory of Computing},
%1987, pp.~1--6.
%
%\item[S69] {\sc V.~Strassen}, Gaussian Elimination Is Not Optimal,
%{\it Numerische Mathematik\/~\bf13}, 1969, pp.~354--356.
%
%\item[P84] {\sc V.~Pan}, {\it How To Multiply Matrices Faster},
%Springer-Verlag, Lecture Notes in Computer Science Vol.~179, 1984.
%
%\end{itemize}

\end{document}