# Complexity of reversible Circuit Value

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?

• 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? Dec 27 '14 at 14:19
• Oh, right. Did not realized it. Yes I guess that the closest to the usual SAT would be to find the inverse.
– Marc
Dec 28 '14 at 2:39
• 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
Dec 28 '14 at 13:52
• @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. Dec 29 '14 at 8:05
• Marzio: The rEQ problem is probably about reversible circuits a well. Dec 29 '14 at 11:28

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 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$.