2
$\begingroup$

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?

$\endgroup$
  • 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$ – Kristoffer Arnsfelt Hansen Dec 27 '14 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 Dec 28 '14 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 Dec 28 '14 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$ – Marzio De Biasi Dec 29 '14 at 8:05
  • $\begingroup$ Marzio: The rEQ problem is probably about reversible circuits a well. $\endgroup$ – Kristoffer Arnsfelt Hansen Dec 29 '14 at 11:28
6
$\begingroup$

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

$\endgroup$
  • $\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 Dec 30 '14 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$ – Kristoffer Arnsfelt Hansen Dec 30 '14 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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