Default reasoning from conditional knowledge bases: Complexity and tractable cases
type: Item
instance of: scholarly article
title: Default reasoning from conditional knowledge bases: Complexity and tractable cases
zbMATH Open document ID: 0952.68139
DOI: 10.1016/S0004-3702(00)00073-4
published in: Artificial Intelligence
publication date: 2000-12-12T00:00:00Z
review text: Conditional knowledge bases have been proposed as belief bases that include defeasible rules (also called defaults) of the form ``\(\phi \rightarrow \psi\)'', which informally read as ``generally, if \(\phi\) then \(\psi\)''. Such rules may have exceptions, which can be handled in different ways. A number of entailment semantics for conditional knowledge bases have been proposed in the literature. However, while the semantic properties and interrelationships of these formalisms are quite well understood, about their computational properties only partial results are known so far. In this paper, we fill these gaps and first draw a precise picture of the complexity of default reasoning from conditional knowledge bases: Given a conditional knowledge base \(KB\) and a default \(\phi \rightarrow \psi\), does \(KB\) entail \(\phi \rightarrow \psi\)? We classify the complexity of this problem for a number of well-known approaches (including Goldszmidt et al.'s maximum entropy approach and Geffner's conditional entailment), where we consider the general propositional case as well as natural syntactic restrictions (in particular, to Horn and literal-Horn conditional knowledge bases). As we show, the more sophisticated semantics for conditional knowledge bases are plagued with intractability in all these fragments. We thus explore cases in which these semantics are tractable, and find that most of them enjoy this property on feedback-free Horn conditional knowledge bases, which constitute a new, meaningful class of conditional knowledge bases. Furthermore, we generalize previous tractability results from Horn to \(q\)-Horn conditional knowledge bases, which allow for a limited use of disjunction. Our results complement and extend previous results, and contribute in refining the tractability/intractability frontier of default reasoning from conditional knowledge bases. They provide useful insight for developing efficient implementations.
Mathematics Subject Classification ID: 68T37
Mathematics Subject Classification ID: 68T30
zbMATH DE Number: 1542378
zbMATH Keywords: reasoning under uncertainty
zbMATH Keywords: conditional knowledge bases
zbMATH Keywords: default reasoning
zbMATH Keywords: nonmonotonic inference
zbMATH Keywords: computational complexity
zbMATH Keywords: polynomial-time algorithms
zbMATH Keywords: Horn knowledge bases and variants
author: Thomas Eiter
author: Thomas Lukasiewicz
describes a project that uses: Smodels
MaRDI profile type: Publication
cites work: The logic of conditionals. An application of probability to deductive logic
cites work: On the logic of theory change: Partial meet contraction and revision functions
cites work: From statistical knowledge bases to degrees of belief
cites work: Mixed integer programming methods for computing nonmonotonic deductive databases
cites work: Nonmonotonic reasoning, conditional objects and possibility theory
cites work: Belief functions and default reasoning
cites work: Polynomial-time inference of all valid implications for Horn and related formulae
cites work: Recognition of \(q\)-Horn formulae in linear time
cites work: Conditional logics of normality: A modal approach
cites work: Unifying default reasoning and belief revision in a modal framework
cites work: On truth-table reducibility to SAT
cites work: The complexity of model checking for circumscriptive formulae
cites work: The complexity of propositional closed world reasoning and circumscription
cites work: Nonmonotonic reasoning: From complexity to algorithms
cites work: Computing with default logic
cites work: A first-order conditional logic for prototypical properties
cites work: On first-order conditional logics
cites work: Q4393480
cites work: Q4012236
cites work: Conditional objects as nonmonotonic consequence relationships
cites work: On the complexity of propositional knowledge base revision, updates, and counterfactuals
cites work: Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
cites work: The complexity of logic-based abduction
cites work: Abduction from logic programs: Semantics and complexity
cites work: Plausibility measures and default reasoning
cites work: Q4296748
cites work: Q4211190
cites work: Q4698061
cites work: Q4198056
cites work: Conditional entailment: bridging two approaches to default reasoning.
cites work: On the consistency of defeasible databases
cites work: Qualitative probabilities for default reasoning, belief revision, and causal modeling
cites work: Complexity Results for Nonmonotonic Logics
cites work: Q4955325
cites work: Q4246971
cites work: Computing functions with parallel queries to NP
cites work: Q4385525
cites work: Propositional knowledge base revision and minimal change
cites work: Hard problems for simple default logics
cites work: Nonmonotonic reasoning, preferential models and cumulative logics
cites work: The complexity of optimization problems
cites work: Q4028809
cites work: Q3493328
cites work: Another perspective on default reasoning
cites work: What does a conditional knowledge base entail?
cites work: The complexity of belief update
cites work: Q4273952
cites work: Circumscription - a form of non-monotonic reasoning
cites work: Nonmonotonic Logic II
cites work: Non-monotonic logic. I
cites work: Semantical considerations on nonmonotonic logic
cites work: Q4028815
cites work: Q4236365
cites work: Q4022226
cites work: Q3221403
cites work: Q3481677
cites work: A logic for default reasoning
cites work: A taxonomy of complexity classes of functions

Default reasoning from conditional knowledge bases: Complexity and tractable cases (cites work)
cites work: Bounded Query Classes

Default reasoning from conditional knowledge bases: Complexity and tractable cases (full work available at URL)
full work available at URL: s0004-3702(00)00073-4

Default reasoning from conditional knowledge bases: Complexity and tractable cases (OpenAlex ID)
OpenAlex ID: W2101013415