On the query complexity of selecting minimal sets for monotone predicates
type: Item
instance of: scholarly article
title: On the query complexity of selecting minimal sets for monotone predicates
zbMATH Open document ID: 1351.68117
author: Mikoláš Janota
author: Joao Marques-Silva
published in: Artificial Intelligence
publication date: 2016-03-08T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68T15
zbMATH DE Number: 6551561
zbMATH Keywords: query complexity
zbMATH Keywords: monotone predicates
zbMATH Keywords: minimal set
zbMATH Keywords: SAT
zbMATH Keywords: backbone
zbMATH Keywords: minimal unsatisfiable set
zbMATH Keywords: minimal correction set
zbMATH Keywords: independent variables
MaRDI profile type: Publication
full work available at URL: j.artint.2016.01.002
OpenAlex ID: W2222364239
Wikidata QID: Q62047278
cites work: Axiom Pinpointing in General Tableaux
cites work: Property-directed incremental invariant generation
cites work: Consequence finding algorithms
cites work: The complexity of selecting maximal solutions
cites work: Algorithms for computing backbones of propositional formulae
cites work: Minimal sets on propositional formulae. Problems and reductions
cites work: Q4198056
cites work: Q4298260
cites work: Removing redundancy from a clause
cites work: Q4359460
cites work: Q4856172
cites work: Q4488342
cites work: Q5503674
cites work: On truth-table reducibility to SAT
cites work: A taxonomy of complexity classes of functions
cites work: The complexity of optimization problems
cites work: Towards an Optimal CNF Encoding of Boolean Cardinality Constraints
cites work: Q5593816
cites work: Oracles That Compute Values
cites work: Q4411161
cites work: Consistent subsets of inconsistent systems: structure and behaviour
cites work: Algorithms for computing minimal unsatisfiable subsets of constraints
cites work: The complexity of facets resolved
cites work: Q5309031
cites work: On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic Applications
cites work: Fixed-Parameter Tractable Reductions to SAT
cites work: Computational Complexity
DBLP publication ID: journals/ai/JanotaM16
DOI: 10.1016/J.ARTINT.2016.01.002
description: scientific article; zbMATH DE number 6551561