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?

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

1 Answer 1


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

  • $\begingroup$ 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. $\endgroup$
    – Marc
    Commented Dec 30, 2014 at 10:25
  • $\begingroup$ The same results holds for circuits built from reversible gates for rCVP and rEQ. However the rSAT problem becomes easy, of course. $\endgroup$ Commented Dec 30, 2014 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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