Answers to SUGGESTED QUIZ (which is actually a digest) * Assuming that $C$ is a complexity class and $S$ is a set of strings, when does the notation $C^S$ makes sense? ANS: This notation presupposes that $C$ is associated with a set of computing devices and that an oracle-utilizing version of these computing devices was defined. * What features of NP and PC are used to show that if NP is in P/poly, then PC has polynomial-size circuits? ANS: The fact that solving each problem in PC is reducible to solving some problem in NP. * What feature of the ternary relation $R$ is used when showing that for every $x$ it holds that "for all y exists z s.t. $(x,y,z)\in R$ if and only if there exists a polynomial-size circuit $C$ such that for all y it holds that $C(x,y)=1$"? (Note: the quantifications over y and z refer to all strings of $\poly(|x|)$-length.) ANS: It uses the hypothesis that the search problem $R'$ has polynomial-size circuits, where $z\in R'((x,y))$ if and only if $(x,y,z)\in R$. Note that $(x,y)$ is an instance of the search problem $R'$ and $z$ is an alleged solution.