The complexity of selecting maximal solutions

DOI10.1006/INCO.1995.1087MaRDI QIDQ1893737zbMATH OpenOpenAlexFDO

Authors Zhi-Zhong Chen, Seinosuke Toda

Publication date 2 August 1995

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2433/83421

zbMATH Keywords

combinatorial optimization problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Recommendations

• More complicated questions about maxima and minima, and some closures of NP
• Optimal satisfiability for propositional calculi and constraint satisfaction problems.
• scientific article; zbMATH DE number 4024790
• Complexity of partial satisfaction. II.
• The parameterized complexity of maximality and minimality problems

Cited in

(27)

• The computational complexity of maximization and integration
• Semantical and computational aspects of Horn approximations
• Minimal sets on propositional formulae. Problems and reductions
• Complexity and expressive power of deterministic semantics for DATALOG^ .
• Max NP-completeness made easy
• Determining inference semantics for disjunctive logic programs
• On the query complexity of selecting minimal sets for monotone predicates
• Generating all maximal models of a Boolean expression
• scientific article; zbMATH DE number 3980537 (Why is no real title available?)
• scientific article; zbMATH DE number 4024790 (Why is no real title available?)
• Complexity results for some eigenvector problems
• The operators min and max on the polynomial hierarchy
• The complexity landscape of outcome determination in judgment aggregation
• Finding similar/diverse solutions in answer set programming
• Introduction to the Maximum Solution Problem
• The Max-Atom Problem and Its Relevance
• Witnesses for Answer Sets of Logic Programs
• Tractability of explaining classifier decisions
• Detecting and repairing anomalous evolutions in noisy environments. Logic programming formalization and complexity results
• Contrastive explanations for answer-set programs
• Hashing-based approximate counting of minimal unsatisfiable subsets
• Trichotomies in the complexity of minimal inference
• On reasoning about access to knowledge
• Explaining multivariate decision trees: characterising tractable languages
• Counting minimal unsatisfiable subsets
• On the complexity of constrained Nash equilibria in graphical games
• Complexity of problem \(TF2|v=1,c=2|C_{\max}\)

This page was built for publication: The complexity of selecting maximal solutions

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