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
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 "garbage" 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'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.
10acomplexity10areversible circuits1 aJordan, Stephen, P. uhttp://dl.acm.org/citation.cfm?id=2685179.2685182