[SOLVED] CS algorithm %

%
% 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.
%

definclsolns{0}
documentclass[12pt]{article}

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

input{macros}

theoremstyle{definition}

ifnuminclsolns=1
ewenvironment{solution}{paragraph{Solution.}}{}
else
ewenvironment{solution}{}{}
excludecomment{solution}
fi

makeatletter
defcollaborators#1{gdef@collaborators{#1}}
def@collaborators{@latex@warning@no@line{No
oexpandcollaborators 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}

ifnuminclsolns=1
makeatletter
oindent 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 dont 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{Im 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}