



01364nas a2200169   4500008004100000022001400041245006300055210006200118260001500180300001600195490000700211520085900218653001501077653002401092100002401116856005401140       2014                        eng d  a1533-714600aStrong Equivalence of Reversible Circuits is coNP-complete0 aStrong Equivalence of Reversible Circuits is coNPcomplete  c2014/11/01  a1302–13070 v143 a<p><span style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 12.8px;">It is well-known that deciding equivalence of logic circuits is a coNP-complete problem. As a corollary, the problem of deciding weak equivalence of reversible circuits, i.e. allowing initialized ancilla bits in the input and ignoring &quot;garbage&quot; ancilla bits in the output, is also coNP-complete. The complexity of deciding strong equivalence, including the ancilla bits, is less obvious and may depend on gate set. Here we use Barrington&#39;s theorem to show that deciding strong equivalence of reversible circuits built from the Fredkin gate is coNP-complete. This implies coNP-completeness of deciding strong equivalence for other commonly used universal reversible gate sets, including any gate set that includes the Toffoli or Fredkin gate.</span></p>10acomplexity10areversible circuits1 aJordan, Stephen, P.  uhttp://dl.acm.org/citation.cfm?id=2685179.2685182