On the query complexity of selecting minimal sets for monotone predicates

DOI10.1016/j.artint.2016.01.002zbMath1351.68117OpenAlexW2222364239WikidataQ62047278 ScholiaQ62047278MaRDI QIDQ253999

Mikoláš Janota, João P. Marques-Silva

Publication date: 8 March 2016

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2016.01.002

zbMATH Keywords

backboneindependent variablesminimal correction setminimal setminimal unsatisfiable setmonotone predicatesquery complexitySAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Witnesses for Answer Sets of Logic Programs, Counting minimal unsatisfiable subsets, Cautious reasoning in ASP via minimal models and unsatisfiable cores, Minimal sets on propositional formulae. Problems and reductions, Computing generating sets of minimal size in finite algebras, Better Paracoherent Answer Sets with Less Resources, Paracoherent answer set computation, Determining inference semantics for disjunctive logic programs, Omission-Based Abstraction for Answer Set Programs, MCS Extraction with Sublinear Oracle Queries, Efficient Reasoning for Inconsistent Horn Formulae

Cites Work

• Removing redundancy from a clause
• Property-directed incremental invariant generation
• The complexity of optimization problems
• The complexity of facets resolved
• On truth-table reducibility to SAT
• A taxonomy of complexity classes of functions
• Minimal sets on propositional formulae. Problems and reductions
• The complexity of selecting maximal solutions
• Algorithms for computing minimal unsatisfiable subsets of constraints
• On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic Applications
• Fixed-Parameter Tractable Reductions to SAT
• Axiom Pinpointing in General Tableaux
• Towards an Optimal CNF Encoding of Boolean Cardinality Constraints
• Oracles That Compute Values
• Consistent subsets of inconsistent systems: structure and behaviour
• Algorithms for computing backbones of propositional formulae
• Computational Complexity
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item