# :memo: Problem Set 1 ###### tags: `pset` :::info ### Instructions - $\LaTeX$ your solutions and submit them on Moodle. - You are welcome to discuss the ideas involved in solving the problems amongst yourselves, but the solutions that you write must be your own. If you have doubts regarding what this means, please talk to me. - **Always cite sources** that gave you the idea for solving a problem, including external sources. If you discussed with a friend, please mention his/her name. This will not affect your grades. - Try to write brief answers. Only write what is necessary and sufficient. - If you don't know an answer, just write what you know and leave the rest. Better still, discuss with me if you are stuck. ::: ### ==Problem 1 [5 marks]== Show that $\mathsf{ZPP} = \mathsf{RP} \cap \mathsf{coRP}$. ### ==Problem 2 [5 marks]== Show that $\mathsf{PP}$ is closed under complementation. ### ==Problem 3 [5 marks]== Use the characterization of the permanent of integer matrices via cycle covers to show that computing the permanent of an integer matrix is in $\mathsf{FP}^{\#\mathsf{SAT}}$. ### ==Problem 4 [5 marks]== Prove that the $\mathsf{BP}$-operator is idempotent. More formally, show that $\mathsf{BP}\cdot \mathsf{BPP} = \mathsf{BPP}$.
Last changed by  
 
yaduv
353
Published on HackMD