The minimum equivalent DNF problem and shortest implicants

DOI10.1006/jcss.2001.1775zbMath1006.68053MaRDI QIDQ1604210

Christopher Umans

Publication date: 4 July 2002

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

Full work available at URL: https://semanticscholar.org/paper/e46cb895f66ae8671bab35200b825c1fdbd1f740

zbMATH Keywords

minimum equivalent DNF problem

Mathematics Subject Classification ID

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Boolean functions with a simple certificate for CNF complexity, The complexity of Boolean formula minimization, The complexity of variable minimal formulas, Disjoint essential sets of implicates of a CQ Horn function, An incremental algorithm for DLO quantifier elimination via constraint propagation, Complexity of DNF minimization and isomorphism testing for monotone formulas, Exclusive and essential sets of implicates of Boolean functions, Approximability of minimum AND-circuits, Abstraction-Based Algorithm for 2QBF

Cites Work

• Unnamed Item
• More complicated questions about maxima and minima, and some closures of NP
• Polynomial-time algorithms for generation of prime implicants
• The polynomial-time hierarchy
• On the computational complexity of some classical equivalence relations on boolean functions
• On limited nondeterminism and the complexity of the V-C dimension
• Classes of bounded nondeterminism
• Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
• Two-level logic minimization: an overview
• On the Amount of Nondeterminism and the Power of Verifying
• A Learning Network Using Adaptive Threshold Elements
• The Problem of Simplifying Truth Functions