%
% To use this as a template for turning in your solutions, change the flag
% \inclsolns from 0 to 1. Make sure you include macros.tex in the directory
% containing this file. Edit the "author" and "collaborators" fields as
% appropriate. Write your solutions where indicated.
%

\def\inclsolns{0}
\documentclass[12pt]{article}

\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{enumerate}
\usepackage{comment}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{hyperref}

\input{macros}

\theoremstyle{definition}

\ifnum\inclsolns=1
\newenvironment{solution}{\paragraph{Solution.}}{}
\else
\newenvironment{solution}{}{}
\excludecomment{solution}
\fi


\makeatletter
\def\collaborators#1{\gdef\@collaborators{#1}}
\def\@collaborators{\@latex@warning@no@line{No \noexpand\collaborators given}}
\makeatother

\author{Ada Lovelace}
\collaborators{Charlie Babbage, Mike Faraday}

\begin{document}


\begin{center}
{\Large CS 535: Complexity Theory, Fall 2020}

\bigskip

{\Large Homework 8}

\smallskip

Due: 2:00AM, Saturday, November 14, 2020.

\end{center}

\ifnum\inclsolns=1
	\makeatletter
	\noindent Name: \@author \\
	Collaborators: \@collaborators
	\makeatother
\else
\fi

\paragraph{Reminder.}
Homework must be typeset with \LaTeX\ preferred. Make sure you understand the course collaboration and honesty policy before beginning this assignment. Collaboration is permitted, but you must write the solutions {\em by
	yourself without assistance}. You must also identify your
collaborators. Assignments missing a collaboration statement will not be accepted. Getting solutions from outside sources such as the
Web or students not enrolled in the class is strictly forbidden.

\bigskip

\setcounter{problem}{-1}
\begin{problem}[Term Paper] Give the paper you are reviewing a careful reading and start thinking about the structure and content of your review. (A draft of your review is due on Nov. 21, so don't delay!)
\end{problem}

\medskip

\begin{problem}[$\NP, \BPP$, and $\RP$] \hfill
	\begin{enumerate}[(a)]
		
		
		\item Suppose $\NP \subseteq \BPP$. Show that $\mathprob{SearchSAT}$ can be solved in randomized polynomial-time. That is, show that there is a probabilistic poly-time algorithm $M$ such that for all satisfiable CNF formulas $\varphi$, we have that $M(\varphi)$ outputs a satisfying assignment to $\varphi$ with probability at least $2/3$. (7 points)
		
		\begin{solution}
			Your solution here.
		\end{solution}
	
		\item Use part (a) to conclude that if $\NP \subseteq \BPP$, then $\NP = \RP$. (5 points)
		
		\begin{solution}
			Your solution here.
		\end{solution}
	\end{enumerate}
\end{problem}


\bigskip


\begin{problem}[Counting Cycles]
	A Hamiltonian cycle in a directed graph $G$ is a cycle that visits every vertex in $G$ exactly once. Define the problem $\mathprob{\#HAM}$\footnote{I'm not so sure about sharp ham, but I like my ham with sharp cheddar.} as follows: Given a directed graph $G$, count the number of Hamiltonian cycles in $G$. It is known that $\mathprob{\#HAM}$ is $\sharpP$-complete. Use this fact to prove that $\mathprob{\#CYCLE}$ is also $\sharpP$-complete. (8 points)
\end{problem}

\begin{solution}
	Your solution here.
\end{solution}

\end{document}






