# :memo: Problem Set 4 ###### tags: `pset mct-21` :::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 [10 marks]== Show that if NP $=$ PCP$(o(\log n),O(1))$, then P=NP. (**Hint:** Use the hypothesis to infer a downward self-reducibility property for SAT) ### ==Problem 2 [10 marks]== Prove that any language $L$ that has a verifier that makes $q$ adaptive queries, also has a verifier that that makes $2^q$ *non-adaptive* queries. ### ==Problem 3 [5 marks]== Show that the problem QUADEQ (discussed in class) is NP-complete. ### ==Problem 4 [10 marks]== Read the proof of Theorem 3.4 from Gil Cohen's [lecture notes](https://eccc.weizmann.ac.il//resources/pdf/cohen.pdf). Use the ideas there to prove the following theorem. *If P=NP, then there is a language in EXP that requires circuits of size $2^{\Omega(n)}$*. This theorem has the same flavor as Ryan William's theorem we saw in class. If you can design fast algorithms, then you can prove circuit lower bounds.