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.

  • $\begingroup$ What is n? Is it fixed or part of the input? $\endgroup$ – Michael Blondin Jan 9 '18 at 13:13
  • $\begingroup$ $n$ is the size of input for the circuit, let me clarify it in the question. $\endgroup$ – Artur Riazanov Jan 9 '18 at 16:01

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.