Complexity classifications for different equivalence and audit problems for Boolean circuits

DOI10.2168/LMCS-8(3:31)2012MaRDI QIDQ3166221zbMATH OpenFDO

Authors Elmar Böhler, Nadia Creignou, Matthias Galota, Henning Schnoor, Heribert Vollmer, S. Reith

Publication date 22 October 2012

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1009.1208

zbMATH Keywords

Boolean circuitsisomorphismcomplexity classification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We study Boolean circuits as a representation of Boolean functions and consider different equivalence, audit, and enumeration problems. For a number of restricted sets of gate types (bases) we obtain efficient algorithms, while for all other gate types we show these problems are at least NP-hard.

Recommendations

• Mathematical Foundations of Computer Science 2003
• The complexity of the descriptiveness of Boolean circuits over different sets of gates
• On the computational complexity of some classical equivalence relations on boolean functions
• The computational complexity of equivalence and isomorphism problems
• The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis

Cited in

(5)

• The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs
• Mathematical Foundations of Computer Science 2003
• Boolean complexity classes vs. their arithmetic analogs
• Parametrised complexity of satisfiability in temporal logic
• The weight in enumeration

This page was built for publication: Complexity classifications for different equivalence and audit problems for Boolean circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3166221)