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

\begin{document}
\input{include.tex}
\homework{2}{Lectures 9-\$}{May 26, 2009}{Jun 10, 2009}

\begin{homeworkProblem}
{\sc (Slice Functions)} \\[2mm]
A function is called a {\em slice function} if for some positive integer $k$, 
\[ 
f(x) = \left\{\begin{array}{lcl}
1 & \textrm{~~if $x$ contains more than $k$ 1's} \\
0 & \textrm{if $x$ contains less than $k$ 1's}
\end{array}\right.
\]
and there are no restrictions when the number of 1s is exactly $k$.
\begin{enumerate}
\item Notice that slice functions are monotone. Show that a general
  circuit computing a slice function can be converted into a monotone
  circuit at the expense of only a polynomial blow up in the size of
  the circuit.
\item Consider the following problem : Given a graph $G$ with $2n$
  vertices, test which of the following is true (1) $G$ has a clique
  of size $n$ or (2) $G$ has at least $\lceil \frac{n(2n-1)}{2}
  \rceil+1$ edges.  This can be shown\footnote{You need not prove it
    in your solutions.} to be $\NP$-coomplete.  Define a sequence of
  slice functions which represents this $\NP$-complete problem.
\end{enumerate}
\end{homeworkProblem}

\begin{homeworkProblem}
{\sc (Super-linear Circuit Lower Bounds)}\\[2mm] As we saw in the
class, it is unknown (and is unlikely because it implies a collapse of
the $\PH$) whether $\NP$ has polynomial sized circuits. That whether
or not $\NP \subseteq \P/\poly$.  On the lower bounds front, in fact,
it is unknown whether there is an explicit function in $\NP$ that does
not have $O(n)$ sized circuits. In this exercise, we will show
something weaker.
\begin{itemize}
\item Show that there is a function in the $\PH$ which does not have
  $O(n)$ sized circuits. (Hint: how does one describe a boolean
  function which can be computed by a circuit of size $k$, but cannot
  be computed by any circuit of size $k'$ where $k' < k$? think of $k$
  as $O(n^2)$ and $k'$ as $O(n)$.)
\item Improve this to show that there is a function in $\Sigma_2^p
  \cap \Pi_2^p$ which does not have $O(n)$ sized circuits.
\end{itemize}
\end{homeworkProblem}

\begin{homeworkProblem}
{\sc (Structural results about randomization)}\\[2mm] Here we will
show some basic structural results about the randomized classes, which
we skipped in class.
\begin{enumerate}
\item Recall the definition of $\ZPP$ as the languages accepted by
  randomized Turing machines (that runs in expected polynomial time)
  which never makes an error (in terms of acceptance), but it can
  answer ``I dont know''. Show that $\ZPP = \RP \cap \co\RP$.
\item A class $A$ is said to be {\em low} for a class $B$ if it is
  true that $A^B = A$. Show that $\BPP$ is {\em low} for itself.
\item Consider a randomized logspace machine $M$. Show that we can
  compute in polynomial time the probability that the machine reaches
  the accepting configuration (Use matrix multplication !).
  Thus show that $\BPL \subseteq \P$.
\end{enumerate}
\end{homeworkProblem}

\begin{homeworkProblem}
{\sc (Query Length and Randomness)} \\[2mm] A polynomial-time oracle
DTM is called a {\em log-query machine} if for any input $x$ of length
and for any oracle $A$, it makes at most $c \log n$ queries, where $c$
is a constant. Let $\Theta_2^{\P}$ denote the class of sets computable
by polynomial-time log-query oracle machines with an oracle in
$\NP$. Prove that $\Theta_2^\P \subseteq \PP$.
\end{homeworkProblem}

\begin{homeworkProblem}
{\sc (Can it be the case that $3\SAT \le_r \overline{3\SAT}$)?} \\[2mm]
A non-deterministic circuit has two inputs $x$ and $y$ (size measured
in terms of $|x|$). We say that it accepts a string $x$ if and only if
there exists a $y$ such that $C(x,y) = 1$. Let $\NP/\poly$ be the
languages that are decided by polynomial sized non-deterministic
circuits. 

\begin{enumerate}
\item We defined the $\BP$ operator in class. Show that $\BP.\NP
  \subseteq \NP/\poly$.
\item Show that if $\overline{3\SAT} \in \BP.\NP$ then $\PH$ collapses
  to $\Sigma_3^p$ (Use ideas similar to Karp-Lipton theorem that we
  already saw). Thus conclude that it is unlikely that $3\SAT \le_r
  \overline{3\SAT}$.
\end{enumerate}
\end{homeworkProblem}
\end{document}
