Verifying that a reduction is correct

Question

Alice has a function $f: \{0,1\}^* \to \{0,1\}^*$ which can be computed in polynomial time. She claims that $x \in \mathrm{SAT} \iff f(x) \in \mathrm{CLIQUE}$. Alice sends the circuit computing $f$ on the set $\{0,1\}^n$ to Bob. Bob is an algorithm from $\mathbf{P}^{\mathrm{SAT}}$ (or even $\mathbf{P}$). He wants to verify that $f$ is indeed a correct reduction of $\mathrm{SAT}$ to $\mathrm{CLIQUE}$ for all the inputs of length $n$. If such Bob exists does it imply the collapse of the polynomial hierarchy?

In other words is $\{C \text{ - circuit }\mid \forall x \in \{0,1\}^n\colon x \in \mathrm{SAT} \iff C(x) \in\mathrm{CLIQUE}\}$ (here $n$ is the number of input gates of $C$). $\Pi_2^P$-complete? $\mathbf{NP}$-hard? Clique and SAT are arbitrary $\mathbf{NP}$-complete languages I've picked.

Answer 1

This is $\Pi_2^p$-complete. Let D be the usual reduction from SAT to CLIQUE. Let w be a string in CLIQUE. Consider a $\Pi_2^p$ language $L$ expressed as the set of $x$ such that for all $y$ there is a $z$ with $(x,y,z)$ in $A$ for some $A$ in P (with polynomial-length bounds on the $y$ and $z$). Let $\phi_{x,y}$ be the formula that will be satisfiable if there exists a $z$ such that $(x,y,z)$ is in $A$.

Define $C_x(\phi)$ as follows: If $\phi=\phi_{x,y}$ for some $y$ then let $C_x(\phi)=w$ otherwise set $C_x(\phi)=D(\phi)$.

Then $x$ is in $L$ if and only if $C_x$ is a reduction from SAT to CLIQUE.