The Minimization Problem for Boolean Formulas

DOI10.1137/S0097539799362639zbMath1008.68054MaRDI QIDQ4785629

Gerd Wechsung, Edith Hemaspaandra

Publication date: 5 January 2003

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

zbMATH Keywords

computational complexityreductionspolynomial hierarchyparallel accessBoolean formula minimization

Mathematics Subject Classification ID

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

Related Items (7)

Redundancy in logic. II: 2CNF and Horn propositional formulae ⋮ Redundancy in logic. III: Non-monotonic reasoning ⋮ The complexity of computing minimal unidirectional covering sets ⋮ The complexity of Boolean formula minimization ⋮ Stability, vertex stability, and unfrozenness for special graph classes ⋮ Isomorphic implication ⋮ Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP

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