The minimum equivalent DNF problem and shortest implicants
From MaRDI portal
Publication:1604210
DOI10.1006/jcss.2001.1775zbMath1006.68053OpenAlexW2046132190MaRDI QIDQ1604210
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
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
