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.