The complexity of Boolean formula minimization
From MaRDI portal
Publication:619911
DOI10.1016/j.jcss.2010.06.011zbMath1218.68089WikidataQ29300594 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/
computational complexity; polynomial-time hierarchy; logic synthesis; formula minimization; Turing reduction
Related Items
A decomposition method for CNF minimality proofs, On the applicability of Post's lattice, Algorithms for computing minimal equivalent subformulas
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