\documentclass[11pt]{article}
\usepackage{preamble}
\usepackage{amsmath,amssymb,complexity,fullpage}

\begin{document}
\input{include.tex}
\homework{1}{Lectures 1-8}{Apr 16, 2009}{Apr 26, 2009}

\begin{homeworkProblem}
{\sc (Padding Arguments)}\\[2mm] 
This problem is to understand a simple technique of {\em padding} to
prove translation results in complexity theory. The idea is to
consider for any language $\L$,
  \[ L_{\sf pad} = \left\{ x.\#^{f(|x|)} | x \in L \right\} \]
where choice of the function $f(.)$ depends on the specific
application in mind. We will do two variants of this.
\begin{enumerate}
\item Show that $\EXP \ne \NEXP \implies \P \ne \NP$.  
Use a similar argument to show that $\P = \L \implies \EXP = \PSPACE$.
\item Prove that $\P \ne \DSPACE(n)$.
\end{enumerate}
\end{homeworkProblem}

\begin{homeworkProblem}
{\sc (Tape Reduction)}\\[2mm]
We saw tape reduction in the class, where we showed how a multi-tape
Turing machine running in time $t(n)$ and space $s(n)$ can be
simulated by a 1-tape Turing machine in time $O(t(n)^2)$ and space
$O(s(n))$. We will show two improvements in this problem.
\begin{enumerate}
  \item Prove that if we are simulating on a 2-tape
    Turing machine, this can be done in $O(t(n) \log t(n))$ and space
    $s(n)$.
  \item If we allow Turing machine to be non-deterministic, then we
    can do tape reduction without a time overhead. Show that a
    multi-tape non-deterministic Turing machine running in time $t(n)$
    can be simulated by a 1-tape non-deterministic Turing machine in
    time $O(t(n))$.
\end{enumerate}
\end{homeworkProblem}

\begin{homeworkProblem}
{\sc (Sparse and Tally Sets)}
\begin{enumerate}
  \item A set $A$ is called {\em sparse} if there is a polynomial $p$,
    such that $|\{ x \in A : |x| = n \}| \le p(n)$. A set $A$ is called
    {\em tally set} if $A \subseteq \{1\}^*$.  \\ Prove that following
    are equivalent.
  \begin{itemize}
  \item Restricted to tally sets $\NP = \P$. That is all tally sets in $\NP$ are in $\P$.
  \item Restricted to sparse sets $\NP = \P$. That is all sparse sets
    in $\NP$ are in $\P$.
  \item $\EXP = \NEXP$. 
  \end{itemize}
  Hence conclude that $\EXP \ne \NEXP \implies \P \ne \NP$ (part(a) of
  the previous problem).
  \item A set $A$ is {\em $\P$-computably sparse} if it is sparse but
    in addition, $|\{ x \in A : |x| = n \}|$ is polynomial time 
    computable. Show that $A \notin \NP \setminus \co\NP$.
\end{enumerate}
\end{homeworkProblem}

\begin{homeworkProblem}
{\sc (Alternation)}\\[2mm] Given an $\epsilon$-free context-free
language $L$ (as its grammer in Chomsky Normal form) the problem of
determining membership of a string in $L$ can be done in $\P$. Prove
this by giving an {\sc ALOG} parsing algorithm.
\end{homeworkProblem}

\begin{homeworkProblem}
{\sc (Skew Circuits)}\\[2mm]
A circuit (with all gates of fan-in 2) is said to be a {\em skew
  circuit} if all negation gates appear at the input every $\land$
gate has at least one input which is a variable or a negation
gate. Circuit Value Problem({\sc CVP}) asks; given a Boolean circuit
and an input to the circuit, check if the circuit evaluates to 1.

\begin{enumerate}
  \item Show that {\sc CVP} restricted to the case when the input is
    skew circuits (call this {\sc Skew-CVP}) is in $\NL$.
  \item Show that Reachability problem reduces to {\sc Skew-CVP} via
    many-one logspace reductions, to {\sc Skew-CVP}. Hence conclude
    that {\sc Skew-CVP} is complete for $\NL$.
\end{enumerate}
\end{homeworkProblem}

\begin{homeworkProblem}
{\sc (Need not be turned in.)}\\

This problem is aimed at testing your understanding of some of the
definitions \& ideas that we discussed in the class. These need not
necessarily be turned in.  But you are welcome to write them down
too.

\begin{itemize}
\item In the proof of Immerman-Szlepsinyi Theorem, to compute $N_k$,
  the number of configurations reachable in at most $k$ steps from
  given configuration $\alpha$ (page 3-2, of notes for lecture 3) why
  cant we use the following simple step instead of the inductive way
  of counting.
  
  {\em for each $k$, to compute $N_k$, we generate each configuration,
    $\beta$ one by one, and for each one non-deterministically verify
    whether $\beta$ is reachable from $\alpha$. If yes, increment the
    count.}
    
\item In lecture 4, we saw $\NP^{\P} \subseteq \NP$. This was argued
  by saying that the non-deterministic oracle machine can simulate the
  membership query to oracle language (which is in $\P$) without
  actually asking the query itself. But now, why wouldn't the same
  strategy work for $\NP^{\NP} \subseteq \NP$ or $\P^{\NP} \subseteq
  \NP$?

\item Suppose $\P=\NP$. That is as sets of subsets of $\Sigma^{*}$,
  $\P$ and $\NP$ are the same. Why does this not imply that $\P^{C} =
  \NP^{C}$ for every $C$? Note that we do know that (as we stated in
  class) there are oracles $C$ for which $\P^{C} \ne \NP^{C}$. If the
  above argument is correct, then we already have $\P \ne \NP$ !!.
\end{itemize}
\end{homeworkProblem}

\end{document}
