Complexity classifications for different equivalence and audit problems for Boolean circuits

DOI10.2168/LMCS-8(3:31)2012zbMATH Open1248.94130arXiv1009.1208MaRDI QIDQ3166221FDOQ3166221

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

Publication date: 22 October 2012

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

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.

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

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

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)

Cited In (4)

• Boolean complexity classes vs. their arithmetic analogs
• Parametrised Complexity of Satisfiability in Temporal Logic
• The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs
• 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)