Monotone Boolean dualization is in co-NP\([\log^{2}n]\).
type: Item
instance of: scholarly article
title: Monotone Boolean dualization is in co-NP\([\log^{2}n]\).
zbMATH Open document ID: 1051.68140
DOI: 10.1016/S0020-0190(02)00346-0
author: Dimitris J. Kavvadias
author: Elias C. Stavropoulos
published in: Information Processing Letters
publication date: 2003-01-21T00:00:00Z
Mathematics Subject Classification ID: 68W05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1856498
zbMATH Keywords: Algorithms
zbMATH Keywords: Computational complexity
zbMATH Keywords: Monotone DNF duality
zbMATH Keywords: Transversal hypergraph
MaRDI profile type: Publication
cites work: Molecular computing, bounded nondeterminism, and efficient recursion
cites work: Complexity of identification and dualization of positive Boolean functions
cites work: Classes of bounded nondeterminism
cites work: New Results on Monotone Dualization and Generating Hypergraph Transversals
cites work: Identifying the Minimal Transversals of a Hypergraph and Related Problems
cites work: On the Complexity of Dualization of Monotone Disjunctive Normal Forms
cites work: On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
cites work: On generating all maximal independent sets
cites work: Generating all maximal models of a Boolean expression
cites work: Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
cites work: NP-completeness: A retrospective
full work available at URL: s0020-0190(02)00346-0
OpenAlex ID: W2087502667
Recommended article: Q3679109
Recommended article: Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
Recommended article: The monotone circuit complexity of Boolean functions
Recommended article: On the Complexity of Dualization of Monotone Disjunctive Normal Forms
Recommended article: Q5202146
Recommended article: Q3822100
Recommended article: Q3758729
Recommended article: Q3335688
Recommended article: On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization
Recommended article: On Berge Multiplication for Monotone Boolean Dualization
description: scientific article; zbMATH DE number 1856498