NIST · ИТ · 2169dbf8ec40c284b009
Strong equivalence of reversible circuits is coNP-complete
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. ignoring the ancilla bits, is also coNP-complete. The complexity of deciding
NIST · ИТОфициальный источник · 2013-07-02
{
"title_en": "Strong equivalence of reversible circuits is coNP-complete",
"designation": "",
"series": "",
"status": "",
"date": "2013-07-02",
"date_original": "July 2, 2013",
"url": "https://www.nist.gov/publications/strong-equivalence-reversible-circuits-conp-complete",
"source": "NIST Publications",
"display_en": "",
"authors_en": "Stephen P. Jordan",
"abstract_excerpt_en": "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. ignoring the ancilla bits, is also coNP-complete. The complexity of deciding",
"id": "2169dbf8ec40c284b009",
"sources": [
"NIST Publications"
],
"source_records": [
{
"title_en": "Strong equivalence of reversible circuits is coNP-complete",
"designation": "",
"series": "",
"status": "",
"date": "2013-07-02",
"date_original": "July 2, 2013",
"url": "https://www.nist.gov/publications/strong-equivalence-reversible-circuits-conp-complete",
"source": "NIST Publications",
"display_en": "",
"authors_en": "Stephen P. Jordan",
"abstract_excerpt_en": "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. ignoring the ancilla bits, is also coNP-complete. The complexity of deciding"
}
],
"translation_state": "none"
}