<p>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 <strong>P</strong> (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$.</p>

<p>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)$.</p>

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

CC BY-SA 3.0
2018-01-09T17:47:35.217Z
2018-01-09T17:47:35.217Z
Lance Fortnow
<p>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?</p>

<p>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.</p>

CC BY-SA 3.0
2018-01-09T13:13:32.050Z
What is n? Is it fixed or part of the input?
Michael Blondin
CC BY-SA 3.0
2018-01-09T16:01:26.883Z
$n$ is the size of input for the circuit, let me clarify it in the question.
Artur Riazanov
<cc.complexity-theory><reductions><np-complete>
Verifying that a reduction is correct
Artur Riazanov
# Verifying that a reduction is correct

(Asked by: username_0 on 2018-01-09)

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.

**Tags:** cc.complexity-theory, reductions, np-complete
> **Comments:**
> **username_1**: What is n? Is it fixed or part of the input?  
> **username_0**: $n$ is the size of input for the circuit, let me clarify it in the question.  

---

## 1 answers

### Answer by username_2 on 2018-01-09. Score: 5 | Accepted answer

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.


---

