The Minimization Problem for Boolean Formulas

DOI10.1137/S0097539799362639MaRDI QIDQ4785629zbMATH OpenFDO

Authors Edith Hemaspaandra, Gerd Wechsung

Publication date 5 January 2003

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

computational complexitypolynomial hierarchyreductionsparallel accessBoolean formula minimization

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• The complexity of Boolean formula minimization
• The Complexity of Boolean Formula Minimization
• scientific article; zbMATH DE number 3867065
• On approximability of Boolean formula minimization
• The Complexity of Very Simple Boolean Formulas with Applications

Cited in

(21)

• The complexity of Boolean formula minimization
• scientific article; zbMATH DE number 7724189 (Why is no real title available?)
• Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
• Stability, vertex stability, and unfrozenness for special graph classes
• scientific article; zbMATH DE number 3867065 (Why is no real title available?)
• scientific article; zbMATH DE number 2210682 (Why is no real title available?)
• scientific article; zbMATH DE number 1822244 (Why is no real title available?)
• Boolean minors
• McColl and minimization
• Isomorphic implication
• Boolean Minimization of Projected Sums of Products via Boolean Relations
• On the boolean minimal realization problem in the max-plus algebra
• scientific article; zbMATH DE number 1782851 (Why is no real title available?)
• Computing smallest MUSes of quantified Boolean formulas
• The Complexity of Boolean Formula Minimization
• scientific article; zbMATH DE number 4000860 (Why is no real title available?)
• On approximability of Boolean formula minimization
• Redundancy in logic. II: 2CNF and Horn propositional formulae
• Redundancy in logic. III: Non-monotonic reasoning
• The Complexity of SPP Formula Minimization
• Minimal False Quantified Boolean Formulas

This page was built for publication: The Minimization Problem for Boolean Formulas

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