The complexity of Boolean formula minimization

DOI10.1016/J.JCSS.2010.06.011MaRDI QIDQ619911zbMATH OpenOpenAlexDBLPWikidataFDO

Authors David Buchfuhrer, Christopher Umans

Publication date 18 January 2011

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://authors.library.caltech.edu/23422/

zbMATH Keywords

computational complexityformula minimizationlogic synthesispolynomial-time hierarchyTuring reduction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Mathematical programming (90C99)

Recommendations

• The Complexity of Boolean Formula Minimization
• The minimum equivalent DNF problem and shortest implicants
• The Minimization Problem for Boolean Formulas
• The Complexity of SPP Formula Minimization
• scientific article; zbMATH DE number 3867065

Cites work

• Circuit minimization problem
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• Minimizing Disjunctive Normal Form Formulas and AC^0 Circuits Given a Truth Table
• The Minimization Problem for Boolean Formulas
• The minimum equivalent DNF problem and shortest implicants
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• The polynomial-time hierarchy

Cited in

(22)

• The minimum equivalent DNF problem and shortest implicants
• On compiling Boolean circuits optimized for secure multi-party computation
• On approximability of Boolean formula minimization
• On the minimization of complexity and automation of efficient representation of Boolean functions in classes of formulas and circuits
• Primitivity, uniform minimality, and state complexity of Boolean operations
• Computing smallest MUSes of quantified Boolean formulas
• scientific article; zbMATH DE number 4172916 (Why is no real title available?)
• The Complexity of Boolean Formula Minimization
• The Complexity of SPP Formula Minimization
• A decomposition method for CNF minimality proofs
• On the applicability of Post's lattice
• Fixed-parameter Approximability of Boolean MinCSPs
• Algorithms for computing minimal equivalent subformulas
• The Minimization Problem for Boolean Formulas
• scientific article; zbMATH DE number 7561759 (Why is no real title available?)
• Minimal False Quantified Boolean Formulas
• Approximating minimum representations of key Horn functions
• The ghosts of forgotten things: a study on size after forgetting
• Constant depth formula and partial function versions of MCSP are hard
• Common equivalence and size of forgetting from Horn formulae
• Explainability via short formulas: the case of propositional logic with implementation
• Computational complexity of quantified Boolean formulas with fixed maximal deficiency

This page was built for publication: The complexity of Boolean formula minimization

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