Monotone Boolean dualization is in co-NP\([\log^{2}n]\).
From MaRDI portal
Publication:1853168
DOI10.1016/S0020-0190(02)00346-0zbMath1051.68140OpenAlexW2087502667MaRDI QIDQ1853168
Elias C. Stavropoulos, Dimitris J. Kavvadias
Publication date: 21 January 2003
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00346-0
Related Items (12)
On the fixed-parameter tractability of the equivalence test of monotone normal forms ⋮ Lattices, closures systems and implication bases: a survey of structural aspects and algorithms ⋮ The Minimal Hitting Set Generation Problem: Algorithms and Computation ⋮ On the complexity of enumerating pseudo-intents ⋮ Complexity of DNF minimization and isomorphism testing for monotone formulas ⋮ Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic ⋮ Computational aspects of monotone dualization: a brief survey ⋮ On the complexity of monotone dualization and generating minimal hypergraph transversals ⋮ On the fractional chromatic number of monotone self-dual Boolean functions ⋮ Resolution based algorithms for the transversal hypergraph generation problem ⋮ Lower bounds for three algorithms for transversal hypergraph generation ⋮ Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs
Cites Work
- Generating all maximal models of a Boolean expression
- On generating all maximal independent sets
- Molecular computing, bounded nondeterminism, and efficient recursion
- On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
- Complexity of identification and dualization of positive Boolean functions
- Classes of bounded nondeterminism
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
- NP-completeness: A retrospective
- New Results on Monotone Dualization and Generating Hypergraph Transversals
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
This page was built for publication: Monotone Boolean dualization is in co-NP\([\log^{2}n]\).