The minimum equivalent DNF problem and shortest implicants

DOI10.1006/jcss.2001.1775zbMath1006.68053OpenAlexW2046132190MaRDI 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

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

Related Items (19)

The complexity of computing minimal unidirectional covering sets ⋮ A decomposition method for CNF minimality proofs ⋮ The complexity of Boolean formula minimization ⋮ Tractability of explaining classifier decisions ⋮ Boolean functions with a simple certificate for CNF complexity ⋮ Matroid Horn functions ⋮ Properties of Switch-List Representations of Boolean Functions ⋮ Boolean functions with long prime implicants ⋮ Complexity of DNF minimization and isomorphism testing for monotone formulas ⋮ Extracting reaction systems from function behavior ⋮ Abstraction-Based Algorithm for 2QBF ⋮ Recognition of tractable DNFs representable by a constant number of intervals ⋮ Exclusive and essential sets of implicates of Boolean functions ⋮ The complexity of variable minimal formulas ⋮ Approximability of minimum AND-circuits ⋮ Disjoint essential sets of implicates of a CQ Horn function ⋮ Approximating Minimum Representations of Key Horn Functions ⋮ Solving QBF with counterexample guided refinement ⋮ An incremental algorithm for DLO quantifier elimination via constraint propagation

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

This page was built for publication: The minimum equivalent DNF problem and shortest implicants