%---------------------------------------------------------------------
% 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}
</div><div class="naked_ctrl">
<form action="/index.cgi/contrast" method="get" name="gate">
<p><a href="http://altstyle.alfasado.net">AltStyle</a> によって変換されたページ <a href="http://www.cs.cmu.edu/~odonnell/complexity/docs/complexity.sty">(-&gt;オリジナル)</a>
/ <label>アドレス: <input type="text" name="naked_post_url" value="http://www.cs.cmu.edu/~odonnell/complexity/docs/complexity.sty" size="22" /></label> <label>モード: <select name="naked_post_mode">
<option value="default">デフォルト</option>
<option value="speech">音声ブラウザ</option>
<option value="ruby">ルビ付き</option>
<option value="contrast" selected="selected">配色反転</option>
<option value="larger-text">文字拡大</option>
<option value="mobile">モバイル</option>
</select>
<input type="submit" value="表示" />
</p>
</form>
</div>