%--------------------------------------------------------------------- % Homework solutions style file for 15-855: Computational Complexity. % % The LaTeX file for a homework in this class should look like the % following: % % \documentclass[11pt]{article} % \usepackage{complexity} % % \Homework{HOMEWORK NUMBER} % \Name{YOUR NAME} % \Collaborators{Detail how you collaborated with other students for this homework.} % % \begin{document} % \MakeHeader % % \section{Problem 1} % Solution to the first problem... % % \section{Problem 2} % Solution to the second problem... % % \bibliography{mybib} % change mybib to the name of your bib file. % % \end{document} %--------------------------------------------------------------------- \usepackage{amsmath,amssymb,amsthm,amsfonts,latexsym,url,xspace} %--------------------------------------------------------------------- % Some useful commands. % % See below for some commands that may be useful in your solutions. % You are of course encouraged to create any other commands that % you find useful. (You can do so at the top of your LaTeX file.) %--------------------------------------------------------------------- % Theorems \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{claim}[theorem]{Claim} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{definition}[theorem]{Definition} % A few complexity classes \renewcommand{\P}{\ensuremath{\mathsf{P}}\xspace} \newcommand{\NP}{\ensuremath{\mathsf{NP}}\xspace} \newcommand{\coNP}{\ensuremath{\mathsf{coNP}}\xspace} \renewcommand{\L}{\ensuremath{\mathsf{L}}\xspace} \newcommand{\NL}{\ensuremath{\mathsf{NL}}\xspace} \newcommand{\PSPACE}{\ensuremath{\mathsf{PSPACE}}\xspace} \newcommand{\NC}{\ensuremath{\mathsf{NC}}\xspace} \newcommand{\Ppoly}{\ensuremath{\mathsf{P/poly}}\xspace} \newcommand{\BPP}{\ensuremath{\mathsf{BPP}}\xspace} \newcommand{\EXP}{\ensuremath{\mathsf{EXP}}\xspace} \newcommand{\IP}{\ensuremath{\mathsf{IP}}\xspace} % Probability statements \renewcommand{\Pr}{{\bf Pr}} \newcommand{\E}{{\bf E}} \newcommand{\Prx}{\mathop{\bf Pr\/}} % these versions with 'x' at the end \newcommand{\Ex}{\mathop{\bf E\/}} % cause the thing you're taking the Pr or E over \newcommand{\Varx}{\mathop{\bf Var\/}} % to appear *underneath* the Pr or E in displayed \newcommand{\Covx}{\mathop{\bf Cov\/}} % equations rather than halfway underneath and to the side % poly and polylog \newcommand{\poly}{\mathrm{poly}} \newcommand{\polylog}{\mathrm{polylog}} % Shortcuts useful for writing functions (i.e. f : \bitsn \to \R) \newcommand{\R}{\mathbb R} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\bits}{\{0,1\}} \newcommand{\bitsn}{\bits^n} % Shortcuts for common greek letters \newcommand{\eps}{\epsilon} \newcommand{\lam}{\lambda} % Shortcuts for common variables \newcommand{\barx}{\overline{x}} \newcommand{\bary}{\overline{y}} \newcommand{\barz}{\overline{z}} \newcommand{\calA}{{\cal A}} \newcommand{\calB}{{\cal B}} \newcommand{\calC}{{\cal C}} % etc. \newcommand{\bx}{{\boldsymbol{x}}} \newcommand{\by}{{\boldsymbol{y}}} % etc. % Smaller operators and fractions \newcommand{\littlesum}{{\textstyle \sum}} % use this if you think the summation sign \newcommand{\littlesumx}{\mathop{{\textstyle \sum}}} % you're getting is too large \newcommand{\half}{{\textstyle \frac12}} % use if you think the \frac12 you're getting is too large %--------------------------------------------------------------------- % Formatting of the document. % % The rest of this file establishes the formatting of the homework % document. There is no need to change -- or even be familiar -- with % any of the following. %--------------------------------------------------------------------- \setlength{\textwidth}{6.5 in} \setlength{\textheight}{9in} \setlength{\oddsidemargin}{0in} \setlength{\topmargin}{0in} \def\NameStr{??} \def\HomeworkStr{??} \def\CollaborationStr{??} \newcommand{\Name}[1]{\def\NameStr{#1}} \newcommand{\Homework}[1]{\def\HomeworkStr{#1}} \newcommand{\Collaboration}[1]{\def\CollaborationStr{#1}} \newcommand{\MakeHeader}{ \noindent{{\bf 15-855: Computational Complexity}} {\hfill {\bf \today}} \begin{center} {\Large \sc Homework \HomeworkStr} \\ \smallskip {\Large\NameStr}\footnote{{\bf Collaboration notice:} \CollaborationStr}\\ \bigskip \begin{tabular}{p{\textwidth}} \hline\\ \end{tabular} \end{center} \vspace{-.2in} } \bibliographystyle{alpha}