Monotone Boolean dualization is in co-NP\([\log^{2}n]\).

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

zbMATH Keywords

AlgorithmsComputational complexityMonotone DNF dualityTransversal hypergraph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

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]\).