5
$\begingroup$

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.

$\endgroup$
  • $\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
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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