Trichotomies in the complexity of minimal inference

DOI10.1007/s00224-011-9320-0zbMath1290.68057MaRDI QIDQ692908

Miki Hermann, Gustav Nordh, Arnaud Durand

Publication date: 6 December 2012

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-011-9320-0

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03B60: Other nonclassical logic

68T27: Logic in artificial intelligence

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bases for Boolean co-clones
• On the relationship between circumscription and negation as failure
• Circumscription - a form of non-monotonic reasoning
• Characterizing diagnoses and systems
• The complexity of model checking for circumscriptive formulae
• The complexity of propositional closed world reasoning and circumscription
• A dichotomy in the complexity of propositional circumscription
• The complexity of minimal satisfiability problems
• Graph minors. XIII: The disjoint paths problem
• The complexity of selecting maximal solutions
• Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
• Closed systems of functions and predicates
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• The Complexity of Circumscriptive Inference in Post’s Lattice
• The algebras of partial functions and their invariants
• Closure properties of constraints
• The complexity of satisfiability problems
• On the Complexity of Some Enumeration Problems for Matroids
• Partial Polymorphisms and Constraint Satisfaction Problems
• Logic for Programming, Artificial Intelligence, and Reasoning
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)