\documentclass[11pt]{article}
\usepackage{amssymb,amsmath,amsthm,url}
\usepackage{graphicx}
%uncomment to get hyperlinks
%\usepackage{hyperref}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Some macros (you can ignore everything until "end of macros")
\def\class{0}
\topmargin 0pt \advance \topmargin by -\headheight \advance
\topmargin by -\headsep
\textheight 8.9in
\oddsidemargin 0pt \evensidemargin \oddsidemargin \marginparwidth
0.5in
\textwidth 6.5in
%%%%%%
\newcommand{\getsr}{\gets_{\mbox{\tiny R}}}
\newcommand{\bits}{\{0,1\}}
\newcommand{\Ex}{\mathbb{E}}
\newcommand{\To}{\rightarrow}
\newcommand{\e}{\epsilon}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\maxpr}{\text{\rm max-pr}}
\newcommand{\cclass}[1]{\mathbf{#1}}
\renewcommand{\P}{\cclass{P}}
\newcommand{\NP}{\cclass{NP}}
\newcommand{\DTIME}{\cclass{DTIME}}
\newcommand{\NTIME}{\cclass{NTIME}}
\newcommand{\SIZE}{\cclass{SIZE}}
\newcommand{\Ppoly}{\cclass{P_{/poly}}}
\newcommand{\SPACE}{\cclass{SPACE}}
\newcommand{\PSPACE}{\cclass{PSPACE}}
\newenvironment{summary}{\begin{quote}\textbf{Summary.}}{\end{quote}}
\newtheorem{theorem}{Theorem}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}{Claim}[theorem]
\theoremstyle{definition}
\newtheorem{exercise}{Exercise}
\newtheorem{definition}{Definition}
\newcommand{\sstart}{\triangleright}
\newcommand{\send}{\triangleleft}
\newcommand{\CSAT}{\ensuremath{\mathsf{CSAT}}}
\newcommand{\SAT}{\ensuremath{\mathsf{3SAT}}}
\newcommand{\IS}{\mathsf{INDSET}}
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\inp}{\mathsf{in}}
\newcommand{\outp}{\mathsf{out}}
\newcommand{\Adv}{\mathsf{Adv}}
\newcommand{\Supp}{\mathsf{Supp}}
\newcommand{\dist}{\Delta}
\newcommand{\indist}{\approx}
\newcommand{\PRG}{\mathsf{G}}
\newcommand{\Enc}{\mathsf{E}}
\newcommand{\Dec}{\mathsf{D}}
\newcommand{\Fcal}{\mathcal{F}}
\newcommand{\Gen}{\mathsf{Gen}}
\newcommand{\Sign}{\mathsf{Sign}}
\newcommand{\Ver}{\mathsf{Ver}}
\newcommand{\Com}{\mathsf{Com}}
\newcommand{\angles}[1]{\langle #1 \rangle}
\newcommand{\eqdef}{\stackrel{\vartriangle}{=}}
\newcommand{\view}{\mathsf{view}}
\newcommand{\trans}{\mathsf{trans}}
\newcommand{\qstart}{q_{\text{\tiny start}}}
\newcommand{\qacc}{q_{\text{\tiny acc}}}
\newcommand{\qrej}{q_{\text{\tiny rej}}}
% end of macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{COS 522 Complexity --- Homework 1.}
\author{Boaz Barak}
\date{Total of 125 points. Due February 20, 2006}
\begin{document}
\maketitle
\noindent\textbf{Important note:} In all the exercises where you are
asked to prove something you need to give a \emph{clearly written}
and \emph{rigorous} proof. If a proof is made up of several steps,
consider encapsulating each step as a separate claim or lemma. While
the proof should be rigorous, remember that it will be read by a
human and not a computer. So while you should be accurate and
convincing, intuition and simplicity are preferred to excessive
formality and verboseness. Use your common sense to decide which
points are clear and obvious, and which deserve more elaboration and
explanations.
You can use results from class, but not results from the text that
were not proven (or at least stated) in class. If you're not sure
whether you can or can not use a particular result, please do not
hesitate to email me.
The recommended way to submit the exercises is to type them up using
\LaTeX . To make this simpler, I will supply the \LaTeX\ source of
the exercises so you can simply copy and paste the questions.
\setcounter{exercise}{-1}
\begin{exercise} Read the assumed knowledge handout. Skim Chapters~1
through 6 of the textbook. Read (or at least skim) Goldreich's text
on computational tasks and models.
\end{exercise}
\begin{exercise}[25 points] The search problem $\CSAT$ is defined as follows:
let $C$ be a Boolean circuit with $n$-bit input and one-bit (i.e.,
binary) output, $\CSAT(C)$ is the set of inputs $x\in\bits^n$ such
that $C(x)=1$. Prove that $\CSAT$ is an $\NP$-complete search
problem via a Karp/Levin reduction.
\end{exercise}
\begin{exercise}[25 points] Prove that the Hamiltonian cycle search problem is an
$\NP$-complete search problem via a Karp/Levin reduction. (You can
use the variant for \emph{directed} graphs if that is easier for
you.)
\end{exercise}
\begin{exercise}[25 points] Suppose that $\P=\NP$. Prove that under this assumption
the decision problem $\Sigma_2$-$\SAT$ can be solved in polynomial
time. This decision problem is defined in the following way: the
input is a statement of the following form:
\[
\exists_{x\!\in\!\bits^n} \; \forall_{y\!\in\!\bits^m} \;
\phi(x,y)\!=\!1
\]
where $\phi$ is a $3CNF$-formula of size polynomial in $n,m$. The
output is $1$ if and only if this statement is true.
\end{exercise}
\begin{exercise}[25 points] If $f:\bits^*\To\bits^*$ is a function,
we denote by $f_n$ the restriction of $f$ to $\bits^n$. Recall that
a Boolean circuit is a labeled bounded in-degree graph. We define
the \emph{size} of such a circuit to be the number of vertices in
the graph. We say that $f \in \Ppoly$ if there are constants $c,d$
such that for every $n$, $f_n$ is computable by a circuit of size
$cn^d$.
Show that $\P \subsetneq \Ppoly$. That is, that every language in
$\P$ is in $\Ppoly$ but there exists a language in $\Ppoly$ that is
not in $\P$.
\end{exercise}
\begin{exercise}[25 points] ~\\
\begin{enumerate}
\item Show that there exists a function $f:\bits^{\ell}\To\bits$
that can not be computed by a circuit of size $2^{\ell/5}$ (under
the definition of size from above).
\item Give a hierarchy theorem for circuits: show that there exists
a function $f:\bits^*\To\bits$ such that for every $n$, $f_n$ can be
computed by an $n^{100}$-sized circuit, but not by an $n^2$-sized
circuit.
\end{enumerate}
See footnote for hint\footnote{\textbf{Hint:} \tiny You might find
it easier to first work with a definition of size of a circuit as
the number of bits to represent the circuit as a string (say, in
adjacency-list format), and then use the fact that the two
definitions are related up to a logarithmic factor.}
\end{exercise}
\end{document}