The complexity of Boolean formula minimization

DOI10.1016/j.jcss.2010.06.011zbMath1218.68089OpenAlexW2070023605WikidataQ29300594 ScholiaQ29300594MaRDI QIDQ619911

Christopher Umans, David Buchfuhrer

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 complexitypolynomial-time hierarchylogic synthesisformula minimizationTuring reduction

Mathematics Subject Classification ID

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

Related Items (6)

A decomposition method for CNF minimality proofs ⋮ On compiling Boolean circuits optimized for secure multi-party computation ⋮ On the applicability of Post's lattice ⋮ Algorithms for computing minimal equivalent subformulas ⋮ Unnamed Item ⋮ Approximating Minimum Representations of Key Horn Functions

Cites Work

• Unnamed Item
• Unnamed Item
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• The polynomial-time hierarchy
• The minimum equivalent DNF problem and shortest implicants
• Circuit minimization problem
• Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
• The Minimization Problem for Boolean Formulas

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