\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}