On the complexity of second-best abductive explanations

DOI10.1016/J.IJAR.2015.05.009zbMATH Open1346.68194arXiv1204.5859OpenAlexW1805424366MaRDI QIDQ899129FDOQ899129

Marco Schaerf, Paolo Liberatore

Publication date: 21 December 2015

Published in: International Journal of Approximate Reasoning (Search for Journal in Brave)

Abstract: While looking for abductive explanations of a given set of manifestations, an ordering between possible solutions is often assumed. The complexity of finding/verifying optimal solutions is already known. In this paper we consider the computational complexity of finding second-best solutions. We consider different orderings, and consider also different possible definitions of what a second-best solution is.

Full work available at URL: https://arxiv.org/abs/1204.5859

zbMATH Keywords

abductionpropositional logicknowledge-based systemsknowledge representation techniques

Mathematics Subject Classification ID

Knowledge representation (68T30) Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence (68T35) Logic in artificial intelligence (68T27)

Cites Work

• Computational Complexity
• Title not available (Why is that?)
• The computational complexity of abduction
• Preprocessing of intractable problems
• Semantics and complexity of abduction from default theories
• Support set selection for abductive and default reasoning
• The complexity of logic-based abduction
• Computer Science Logic
• A Complete Classification of the Complexity of Propositional Abduction
• Abduction from logic programs: Semantics and complexity
• On some tractable classes in deduction and abduction
• Monotonic reductions, representative equivalence, and compilation of intractable problems
• Title not available (Why is that?)
• What makes propositional abduction tractable
• Complexity Classifications for Propositional Abduction in Post's Framework
• Title not available (Why is that?)
• On the complexity of second-best abductive explanations
• Counting complexity of propositional abduction

Cited In (1)

• On the complexity of second-best abductive explanations

This page was built for publication: On the complexity of second-best abductive explanations

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