<p>For rCVP, we can reduce the usual CVP problem to rCVP as follows. Given a circuit $C$ on $n$ inputs, produce a circuit $C'$ that on input $x=(x_0,x_1,\dots,x_n)$ outputs $C'(x)=(x_0 \oplus C(x_1,\dots,x_n),x_1,x_2,\dots,x_n)$.</p>

<p>For rEQ, we can similarly reduce the UNSAT problem (modifying the suggestion of Marzio De Biasi). Namely, given a formula $\varphi$ on $n$ variables, let $C_1$ on input $x=(x_0,x_1,\dots,x_n)$ output $(x_0 \oplus \varphi(x_1,\dots,x_n),x_1,\dots,x_n)$ and $C_2$ simply output $x$.</p>

CC BY-SA 3.0
2014-12-30T10:25:19.010Z
OK, looks good.

Appendix question: what if we ask that the circuit is built using only reversible *gates* (like Toffoli's gate)?
I guess people from quantum computing have studied this question.
Marc
CC BY-SA 3.0
2014-12-30T23:51:02.317Z
The same results holds for circuits built from reversible gates for rCVP and rEQ. However the rSAT problem becomes easy, of course.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2014-12-29T11:52:40.260Z
2014-12-29T12:12:20.403Z
2014-12-29T12:12:20.403Z
Kristoffer Arnsfelt Hansen
<p>I am wondering what is known about the complexity of the reversible Circuit Value Problem (rCVP) and the corresponding reversible Satisfiability problem (rSAT).</p>

<p>More precisely: a circuit $B^n\rightarrow B^n$ on $n$ boolean values is reversible if it computes an invertible function. </p>

<p>The rCVP problem is: <em>given a reversible circuit on $n$ boolean values and $n$ inputs, what is the value of the output?</em></p>

<p>The rSAT problem is: <em>given a reversible circuit, what is the input that yields the output $1,\dots,1$?</em> (function problem, see comments)</p>

<p>As subcases of their non-reversible versions (CVP and SAT) these problem are respectively in Ptime and NP.</p>

<p>My question is rather about hardness: is rCVP Ptime-complete? Is rSAT NP-complete? I am no specialist of this and looked for a statement of the result, but found nothing so far. I read that one can encode any usual circuit by a reversible circuit using Toffoli's gates, but the is size of the reversible circuit one obtains doing so polynomial in the size of the initial circuit?</p>

CC BY-SA 3.0
2014-12-27T14:19:34.623Z
For rSAT, the answer is always yes! You may be interested in the (function) problem of finding the inverse instead. For both of rCVP and rSAT, how do you ensure that the circuits are reversible? Or do you consider the problems as promise-problems?
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2014-12-28T02:39:00.853Z
Oh, right. Did not realized it. Yes I guess that the closest to the usual SAT would be to find the inverse.
Marc
CC BY-SA 3.0
2014-12-28T13:52:17.417Z
Also, what about the equivalence problem (r)EQ: given two circuits, do they yield the same output if they are fed the same input?
rEQ is co-NP, but is it co-NP complete?
Marc
CC BY-SA 3.0
2014-12-29T08:05:48.423Z
@Marc: rEQ is co-NP complete, to prove it you can use a reduction from UNSAT: compare the circuit for the formula $\varphi$ to the circuit that always outputs $0$, the two are equivalent if and only if $\varphi$ is unsatisfiable.
Marzio De Biasi
CC BY-SA 3.0
2014-12-29T11:28:51.883Z
Marzio: The rEQ problem is probably about reversible circuits a well.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2014-12-29T13:28:50.207Z
@KristofferArnsfeltHansen: umm I thought the difficult part was the reduction (the r in the comment above is among parentheses) :( ... your answer is clear!
Marzio De Biasi
CC BY-SA 3.0
2014-12-29T13:33:39.270Z
You are probably right.
Kristoffer Arnsfelt Hansen
<cc.complexity-theory><circuit-complexity><sat>
Complexity of reversible Circuit Value
Marc
# Complexity of reversible Circuit Value

(Asked by: username_0 on 2014-12-27)

I am wondering what is known about the complexity of the reversible Circuit Value Problem (rCVP) and the corresponding reversible Satisfiability problem (rSAT).

More precisely: a circuit $B^n\rightarrow B^n$ on $n$ boolean values is reversible if it computes an invertible function.

The rCVP problem is: *given a reversible circuit on $n$ boolean values and $n$ inputs, what is the value of the output?*

The rSAT problem is: *given a reversible circuit, what is the input that yields the output $1,\dots,1$?* (function problem, see comments)

As subcases of their non-reversible versions (CVP and SAT) these problem are respectively in Ptime and NP.

My question is rather about hardness: is rCVP Ptime-complete? Is rSAT NP-complete? I am no specialist of this and looked for a statement of the result, but found nothing so far. I read that one can encode any usual circuit by a reversible circuit using Toffoli's gates, but the is size of the reversible circuit one obtains doing so polynomial in the size of the initial circuit?

**Tags:** cc.complexity-theory, circuit-complexity, sat

> **Comments:**
> **username_1**: For rSAT, the answer is always yes! You may be interested in the (function) problem of finding the inverse instead. For both of rCVP and rSAT, how do you ensure that the circuits are reversible? Or do you consider the problems as promise-problems?  
> **username_0**: Oh, right. Did not realized it. Yes I guess that the closest to the usual SAT would be to find the inverse.  
> **username_0**: Also, what about the equivalence problem (r)EQ: given two circuits, do they yield the same output if they are fed the same input? rEQ is co-NP, but is it co-NP complete?  
> **username_2**: @username_0: rEQ is co-NP complete, to prove it you can use a reduction from UNSAT: compare the circuit for the formula $\varphi$ to the circuit that always outputs $0$, the two are equivalent if and only if $\varphi$ is unsatisfiable.  
> **username_1**: Marzio: The rEQ problem is probably about reversible circuits a well.  
> **username_2**: @KristofferArnsfeltHansen: umm I thought the difficult part was the reduction (the r in the comment above is among parentheses) :( ... your answer is clear!  
> **username_1**: You are probably right.  

---

## 1 answers

### Answer by username_1 on 2014-12-29. Score: 6 | Accepted answer

For rCVP, we can reduce the usual CVP problem to rCVP as follows. Given a circuit $C$ on $n$ inputs, produce a circuit $C'$ that on input $x=(x\_0,x\_1,\dots,x\_n)$ outputs $C'(x)=(x\_0 \oplus C(x\_1,\dots,x\_n),x\_1,x\_2,\dots,x\_n)$.

For rEQ, we can similarly reduce the UNSAT problem (modifying the suggestion of username_2). Namely, given a formula $\varphi$ on $n$ variables, let $C\_1$ on input $x=(x\_0,x\_1,\dots,x\_n)$ output $(x\_0 \oplus \varphi(x\_1,\dots,x\_n),x\_1,\dots,x\_n)$ and $C\_2$ simply output $x$.

> **Comments:**
> **username_0**: OK, looks good.  Appendix question: what if we ask that the circuit is built using only reversible *gates* (like Toffoli's gate)? I guess people from quantum computing have studied this question.  
> **username_1**: The same results holds for circuits built from reversible gates for rCVP and rEQ. However the rSAT problem becomes easy, of course.  

---

