Monotone Boolean dualization is in co-NP[^2n].

DOI10.1016/S0020-0190(02)00346-0MaRDI QIDQ1853168zbMATH OpenOpenAlexFDO

Authors Dimitris J. Kavvadias, Elias C. Stavropoulos

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)

Recommendations

• scientific article; zbMATH DE number 3900678
• Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
• The monotone circuit complexity of Boolean functions
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• scientific article; zbMATH DE number 4193610
• scientific article; zbMATH DE number 4095386
• scientific article; zbMATH DE number 4008289
• scientific article; zbMATH DE number 3867233
• On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization
• On Berge Multiplication for Monotone Boolean Dualization

Cites work

• Classes of bounded nondeterminism
• Complexity of identification and dualization of positive Boolean functions
• Generating all maximal models of a Boolean expression
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Molecular computing, bounded nondeterminism, and efficient recursion
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• NP-completeness: a retrospective
• On generating all maximal independent sets
• On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations

Cited in

(19)

• On the fractional chromatic number of monotone self-dual Boolean functions
• Lower bounds for three algorithms for transversal hypergraph generation
• Lattices, closures systems and implication bases: a survey of structural aspects and algorithms
• Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
• Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs
• Resolution based algorithms for the transversal hypergraph generation problem
• On the fixed-parameter tractability of the equivalence test of monotone normal forms
• The minimal hitting set generation problem: algorithms and computation
• On Berge Multiplication for Monotone Boolean Dualization
• A duality between Boolean functions
• A Fast and Simple Parallel Algorithm for the Monotone Duality Problem
• Achieving new upper bounds for the hypergraph duality problem through logic
• Experimental comparison of the two Fredman-Khachiyan-algorithms
• Left-to-right multiplication for monotone Boolean dualization
• On the complexity of enumerating pseudo-intents
• New theoretical results on the monotone Boolean duality and the monotone Boolean dualization problems
• Complexity of DNF minimization and isomorphism testing for monotone formulas
• Computational aspects of monotone dualization: a brief survey
• On the complexity of monotone dualization and generating minimal hypergraph transversals

This page was built for publication: Monotone Boolean dualization is in co-NP\([\log^{2}n]\).

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853168)