\documentclass[12pt]{article}
%\usepackage{concrete}

\topmargin=-1in
\oddsidemargin=0in
\textwidth=6.5in
\textheight=9in

\begin{document}
\title{Computational Complexity\\CSC 2401 --- Assignment 3}
\author{Behdad Esfahbod\\993505827}
\maketitle
\begin{enumerate}

\item % 1
False.

\noindent\emph{Proof} Let $L$ be a problem in $\Sigma_k^P-\Sigma_{k-1}^P$ problem for some $k\geq
1$.  By assumption such a problem exists.
As $\Sigma_k^P=NP^{\Sigma_{k-1}^P}$, there exists $B\in \Sigma_{k-1}^P$ such
that $L\in NP^{B}$.  
As $\Sigma_{k-1}^P=NP^{\Sigma_{k-2}^P}$,
then $B\in NP^{\Sigma_{k-2}^P}$.
We are almost done now.  We chose $L$ so that $L\not\in
NP^{\Sigma_{k-2}^P}=\Sigma_{k-1}^P$ but $B\in NP^{\Sigma_{k-2}^P}$.  This is a
couter-example to the statement in question.  The proof is complete.

\item % 2
I solve the first problem:

We construct $L\in E^{PH}$ such that for input $x$, it computes $C_n(x)$ where
$n=|x|$ and $C_n$ is a circuit of size $MAXC(n)$ and no smaller circuit computes
the same function as $C_n$.  Apparently $L$ holds the properties that we want.

We use the following oracle:

\begin{eqnarray*}
MAXCIRCUIT=&\{&(x,c,d,y)| \exists C\forall C':\\
    &&|y|=2^{|x|}, \\
    &&c \mbox{ is a prefix of } C, \\
    &&C \mbox{ is a circuit with $|x|$ inputs and $SIZE(C)=d$},\\
    &&SIZE(C')<SIZE(C),\\
    &&C' \mbox{ is not equivalent to } C\\
    &\}
\end{eqnarray*}

We observe that $MAXCIRCUIT(x,c,d,1^|x|)$ is the language of all 
circuits that are extensions of $c$ and accept input of length $|x|$ and
of size $d$ and with no shorter circuit computing the same function.  As the
size of input ($y$) is exponential in $|x|$, checking these conditions can be
done in polynomial time in input length and so $MAXCIRCUIT$ is in $PH$.

Now we construct $L$ by providing an Oracle TM $M$ that on input $x$, first finds
$MAXC(|x|)$, then finds a suitable circuit of that size bit by bit:

\begin{quotation}
\noindent\obeylines\obeyspaces
\def\m{\mbox{}}
On input $x$ do:
\m
\m for $i$ = $\frac{2^{n+1}}{n}$ downto $\frac{2^n}{n}$ do
\m     if $MAXCIRCUIT(x, \epsilon, i, 1^{|x|}) == Accept$ then
\m         break
\m // Now $i=MAXC(|x|)$
\m 
\m $c := \epsilon$
\m for $j$ = 1 to $i$ do
\m     if $MAXCIRCUIT(x, c0, i, 1^{|x|}) == Accept$ then
\m         $c := c0$
\m     else
\m         $c := c1$
\m // Now $c$ is a minimal circuit of size $MAXC(|x|)$
\m
\m Simulate circuit $c$ with input $x$
\m If it returns $True$ then
\m     return $Accept$
\m else
\m     return $Reject$
\end{quotation}

Now $L=L(M)$ is a language that $\forall n [L]_n$ requires $MAXC(n)$ circuit size.

\begin{itemize}
\item We know that $PH\subset PSPACE$, and $E\subset ESPACE$,
so every language in $E^{PH}$ is also in $ESPACE^{PSPACE}$ which is equal to $ESPACE$.
\item
We proof the contrapositive side.  If $P=NP$ then $P=PH$ and so $E^{PH}=E$.  The
original statement of the problem then becomes that there exists a language in
$E$ such that $\forall n[L]_n$ requires $MAXC(n)$ circuit size.  This is
equivalent to what we are asked for to prove.
\end{itemize}

\item % 3
All our concern goes to the cases that in the proof of $\overline{TRE}$ is
$PSPACE$-complete, where the length of the output regular expression is related
by $s(n)$ the space requirement.  After having a look, we find that there are a
few places that we have things like $\Gamma_1^{s(n)+1}$ or $\Gamma^{s(n)-n}$ or
$(\Gamma_1 \oplus \{\lambda\})^{s(n)-1}$.  All of these cases are in the form
$R^a$ where $a$ is $O(s(n))$.  The usual encoding of these in language of
$\overline{TRE}$ is to repeat reqular expression for $R$ connected with
$\oplus$ with each other $a$ times, which makes the final regular expression
$\Theta(s(n))$.

Now we show how we can encode $R^a$ in a small repeatings of the regular
expression for $R$ using \emph{squaring} operation.
To be more exact, in only $\lceil \log(a)\rceil$ repeatations.
Here is the recursive construction:

\noindent\textbf{Lemma\space} For any regular expression $R$ and positive integer $a$,
the regular expression $R^a$ which is $R\oplus R\oplus \dots \oplus R$ ($a$
occurences of $R$), can be written as a squegular expression with
length bounded by $|R|\log(a)$.

\noindent\emph{proof}  We construct the squegular expression by induction.  For 
$a=1$, the regular expression for $R$ is a squegular expression for $R^1$ too.
For $a>1$, there are two cases that we consider:
\begin{itemize}
\item $a$ is even:  Let $T$ be $R^{a/2}$ constructed by induction.  $R^a$
now can be writte as $T^S$ as a squegular expression.
\item $a$ is odd:  Let $T$ be $R^{(a-1)/2}$ constructed by induction.  $R^a$
now can be writte as $T^S\oplus R$ as a squegular expression.
\end{itemize}
The lenght of the squegular expression for $R^a$ is bounded by recursion
$|R^a|=|R^{\lfloor a/2 \rfloor}|+|R|+O(1)$ which is bounded by $|R|\log(a)$.

\bigskip

Now using the above lemma, we get a squegular expression which relates to $s(n)$
with $O(\log(s(n)))$.  Means that that our resulting squegular expression is 
polynomial in $n$ for $s(n)\in cn^d$,
which in turn means $\overline{TSRE}$ is complete for
ESPACE.

\end{enumerate}
\end{document}