A Survey on Complexity Results for Non-monotonic Logics
---
paper_title: Circumscription - A Form of Non-Monotonic Reasoning

paper_content:

Humans and intelligent computer programs must often jump to the conclusion that the objects they can determine to have certain properties or relations are the only objects that do. Circumscription formalizes such conjectural reasoning.
---
paper_title: Propositional circumscription and extended closed-world reasoning are ΠP2-complete

paper_content:

Abstract Circumscription and the closed-world assumption with its variants are well-known nonmonotonic techniques for reasoning with incomplete knowledge. Their complexity in the propositional case has been studied in detail for fragments of propositional logic. One open problem is whether the deduction problem for arbitrary propositional theories under the extended closed-world assumption or under circumscription is Π P 2 -complete, i.e., complete for a class of the second level of the polynomial hierarchy. We answer this question by proving these problems Π P 2 -complete, and we show how this result applies to other variants of closed-world reasoning.
---
paper_title: Computing Circumscription

paper_content:

Circumscription is a transformation of predicate formulas proposed by John McCarthy for the purpose of formalizing non-monotonic aspects of commonsense reasoning. Circumscription is difficult to implement because its definition involves a second-order quantifier. This paper presents metamathematical results that allow us in some cases to replace circumscription by an equivalent first-order formula.
---
paper_title: APPLICATIONS OF CIRCUMSCRIPTION TO FORMALIZING COMMON SENSE KNOWLEDGE

paper_content:

We present a new and more symmetric version of the circumscription method of nonmonotonic reasoning first described in (McCarthy 1980) and some applications to formalizing common sense knowledge. The applications in this paper are mostly based on minimizing the abnormality of different aspects of various entities. Included are nonmonotonic treatments of is-a hierarchies, the unique names hypothesis, and the frame problem. The new circumscription may be called formula circumscription to distinguish it from the previously defined domain circumscription and predicate circumscription. A still more general formalism called prioritized circumscription is briefly explored.
---
paper_title: Computational Complexity of Hypothesis Assembly

paper_content:

T h e p rob lem of f inding a best exp lana t ion of a set of da ta has been a top ic of m u c h interest in A r t i f i c i a l I n t e l l i gence. In th is paper we present an approach to th is p r o b l e m by hypothesis assembly. We present th is approach f o rma l l y so tha t we can examine the t ime comp lex i t y and correctness of the a lgo r i t hms . We then examine a system i m p l e m e n t e d using th is approach , w h i c h per fo rms red b lood a n t i b o d y iden t i f i ca t ion . We use th is d o m a i n to examine the r a m i f icat ions of the assumpt ions of the f o r m a l model in a real wo r l d s i t ua t i on . We also br ie f ly compare th is approach to other assembly approaches in te rms o f t i m e comp lex i t y and rel iance on assumpt ions. I . I n t r o d u c t i o n T h e p rob lem of abduc t i ve reasoning (as proposed by the phi losopher C.S. Peirce) has been a topic of m u c h recent interest in A r t i f i c i a l Inte l l igence ( M i l l e r 1982, Reggia 1983, Cha rn iak 1985). T h e general task faced by an abduc t i ve reasoning system is to find the best exp lana t ion of a set of da ta or observat ions, i.e., the best way to account for a set of da ta . Mos t of the work in A r t i f i c i a l Inte l l igence in th is area has focused on a specific k i nd of a b d u c t i o n , wh ich we cal l hypothes is assembly. T h e hypothesis assembly task assumes as g iven a set of hypotheses w i t h some knowledge about what sorts of da ta each can account for , and f inds the subset of these hypotheses tha t best accounts for the p rob lem da ta . A t the O h i o State Labo ra to ry for A r t i f i c i a l In te l l igence, Josephson et . a l . (1985) have been deve lop ing an approach for a b d u c t i o n based upon hypothesis assembly. In th is paper we w i l l begin by present ing a m a t h e m a t i cal idea l iza t ion of th is approach . F r o m th is we w i l l analyze the comp lex i t y and correctness o f the a l g o r i t h m . T h e n we w i l l examine how wel l th is idea l iza t ion matches w i t h real T h i s wo rk has been suppor ted by the N a t i o n a l L i b ra r y o f Med ic ine under g ran t LM-04298 , the N a t i o n a l Science F o u n d a t i o n t h r o u g h a Gradua te Fe l lowsh ip , and the Defense Advanced Research Pro jec ts Agency, R A D C cont rac t F30602-85-C-0010. C o m p u t e r faci l i t ies were enhanced t h r o u g h gi f ts f r o m Xe rox C o r p o r a t i o n . wor ld concepts o f abduc t i on . In pa r t i cu la r , we w i l l examine a system cal led R E D , based upon th is app roach , wh ich performs an t i body iden t i f i ca t i on in the d o m a i n o f red b lood cell t y p i n g , as descr ibed in (Josephson 1984), (Josephson 1985) and ( S m i t h 1985), and show how the general ma thema t i ca l results respond to quest ions t ha t have been raised ( M o s t o w 1985) about i ts comp lex i t y . I I . M a t h e m a t i c a l I d e a l i z a t i o n o f A b d u c t i o n D e f i n i t i o n s In order to mot i va te the fo l low ing de f in i t ions , we w i l l examine br ief ly the d o m a i n o f the cu r ren t i m p l e m e n t a t i o n o f R E D , the d o m a i n o f b l ood bank a n t i b o d y analysis. T h e p r i mary da ta consists of results of several lab tests on b l ood samples. T h e b lood bank technologist knows how antibodies can account for var ious react ions. T h e lab tests have the p roper ty t ha t i f a n t i b o d y A accounts for some react ion r, and an t i body B accounts for react ion q, then the presence of bo th ant ibod ies A and B accounts for b o t h react ions r and q. T h i s p rope r t y of a doma in w i l l be referred to as independence of hypotheses. More fo rma l l y , we define a d o m a i n for hypothes is assembly as a the t r i p l e (H, M,e) , where H is a finite set of hypotheses, M is a finite set of manifestations, and c is a map f r o m subsets of H to subsets of M. e(S) is i n te rpre ted as the explanatory power of a set of hypotheses, and is the set of mani fes ta t ions for wh i ch those hypo the ses can account . An assembly p rob lem is specif ied by a subset Mo M. Mo is i n te rp re ted as the set of observed mani fes ta t ions 1 . In these te rms, we have The Independence Assumption: If S and T are subsets of H, then A l t h o u g h m a n y domains satisfy the independence ass u m p t i o n , we w ish to s t rengthen ou r result by rep lac ing 1 In wha t fo l lows, we w i l l use the no ta t i on e(S) where we shou ld , s t r i c t l y speak ing , w r i t e for the res t r i c t i on of e(S) to the observed man i fes ta t ions .
---
paper_title: Propositional circumscription and extended closed-world reasoning are ΠP2-complete

paper_content:

Abstract Circumscription and the closed-world assumption with its variants are well-known nonmonotonic techniques for reasoning with incomplete knowledge. Their complexity in the propositional case has been studied in detail for fragments of propositional logic. One open problem is whether the deduction problem for arbitrary propositional theories under the extended closed-world assumption or under circumscription is Π P 2 -complete, i.e., complete for a class of the second level of the polynomial hierarchy. We answer this question by proving these problems Π P 2 -complete, and we show how this result applies to other variants of closed-world reasoning.
---
paper_title: Abductive and default reasoning: a computational core

paper_content:

Of all the possible ways of computing abductive explanations, the ATMS procedure is one of the most popular. While this procedure is known to run in exponential time in the worst case, the proof actually depends on the existence of queries with an exponential number of answers. But how much of the difficulty stems from having to return these large sets of explanations? Here we explore abduction tasks similar to that of the ATMS, but which return relatively small answers. The main result is that although it is possible to generate some non-trivial explanations quickly, deciding if there is an explanation containing a given hypothesis is NP-hard, as is the task of generating even one explanation expressed in terms of a given set of assumption letters. Thus, the method of simply listing all explanations, as employed by the ATMS, probably cannot be improved upon. An interesting result of our analysis is the discovery of a subtask that is at the core of generating explanations, and is also at the core of generating extensions in Reiter's default logic. Moreover, it is this subtask that accounts for the computational difficulty of both forms of reasoning. This establishes for the first time a strong connection between computing abductive explanations and computing extensions in default logic.
---
paper_title: Computational Complexity of Hypothesis Assembly

paper_content:

T h e p rob lem of f inding a best exp lana t ion of a set of da ta has been a top ic of m u c h interest in A r t i f i c i a l I n t e l l i gence. In th is paper we present an approach to th is p r o b l e m by hypothesis assembly. We present th is approach f o rma l l y so tha t we can examine the t ime comp lex i t y and correctness of the a lgo r i t hms . We then examine a system i m p l e m e n t e d using th is approach , w h i c h per fo rms red b lood a n t i b o d y iden t i f i ca t ion . We use th is d o m a i n to examine the r a m i f icat ions of the assumpt ions of the f o r m a l model in a real wo r l d s i t ua t i on . We also br ie f ly compare th is approach to other assembly approaches in te rms o f t i m e comp lex i t y and rel iance on assumpt ions. I . I n t r o d u c t i o n T h e p rob lem of abduc t i ve reasoning (as proposed by the phi losopher C.S. Peirce) has been a topic of m u c h recent interest in A r t i f i c i a l Inte l l igence ( M i l l e r 1982, Reggia 1983, Cha rn iak 1985). T h e general task faced by an abduc t i ve reasoning system is to find the best exp lana t ion of a set of da ta or observat ions, i.e., the best way to account for a set of da ta . Mos t of the work in A r t i f i c i a l Inte l l igence in th is area has focused on a specific k i nd of a b d u c t i o n , wh ich we cal l hypothes is assembly. T h e hypothesis assembly task assumes as g iven a set of hypotheses w i t h some knowledge about what sorts of da ta each can account for , and f inds the subset of these hypotheses tha t best accounts for the p rob lem da ta . A t the O h i o State Labo ra to ry for A r t i f i c i a l In te l l igence, Josephson et . a l . (1985) have been deve lop ing an approach for a b d u c t i o n based upon hypothesis assembly. In th is paper we w i l l begin by present ing a m a t h e m a t i cal idea l iza t ion of th is approach . F r o m th is we w i l l analyze the comp lex i t y and correctness o f the a l g o r i t h m . T h e n we w i l l examine how wel l th is idea l iza t ion matches w i t h real T h i s wo rk has been suppor ted by the N a t i o n a l L i b ra r y o f Med ic ine under g ran t LM-04298 , the N a t i o n a l Science F o u n d a t i o n t h r o u g h a Gradua te Fe l lowsh ip , and the Defense Advanced Research Pro jec ts Agency, R A D C cont rac t F30602-85-C-0010. C o m p u t e r faci l i t ies were enhanced t h r o u g h gi f ts f r o m Xe rox C o r p o r a t i o n . wor ld concepts o f abduc t i on . In pa r t i cu la r , we w i l l examine a system cal led R E D , based upon th is app roach , wh ich performs an t i body iden t i f i ca t i on in the d o m a i n o f red b lood cell t y p i n g , as descr ibed in (Josephson 1984), (Josephson 1985) and ( S m i t h 1985), and show how the general ma thema t i ca l results respond to quest ions t ha t have been raised ( M o s t o w 1985) about i ts comp lex i t y . I I . M a t h e m a t i c a l I d e a l i z a t i o n o f A b d u c t i o n D e f i n i t i o n s In order to mot i va te the fo l low ing de f in i t ions , we w i l l examine br ief ly the d o m a i n o f the cu r ren t i m p l e m e n t a t i o n o f R E D , the d o m a i n o f b l ood bank a n t i b o d y analysis. T h e p r i mary da ta consists of results of several lab tests on b l ood samples. T h e b lood bank technologist knows how antibodies can account for var ious react ions. T h e lab tests have the p roper ty t ha t i f a n t i b o d y A accounts for some react ion r, and an t i body B accounts for react ion q, then the presence of bo th ant ibod ies A and B accounts for b o t h react ions r and q. T h i s p rope r t y of a doma in w i l l be referred to as independence of hypotheses. More fo rma l l y , we define a d o m a i n for hypothes is assembly as a the t r i p l e (H, M,e) , where H is a finite set of hypotheses, M is a finite set of manifestations, and c is a map f r o m subsets of H to subsets of M. e(S) is i n te rpre ted as the explanatory power of a set of hypotheses, and is the set of mani fes ta t ions for wh i ch those hypo the ses can account . An assembly p rob lem is specif ied by a subset Mo M. Mo is i n te rp re ted as the set of observed mani fes ta t ions 1 . In these te rms, we have The Independence Assumption: If S and T are subsets of H, then A l t h o u g h m a n y domains satisfy the independence ass u m p t i o n , we w ish to s t rengthen ou r result by rep lac ing 1 In wha t fo l lows, we w i l l use the no ta t i on e(S) where we shou ld , s t r i c t l y speak ing , w r i t e for the res t r i c t i on of e(S) to the observed man i fes ta t ions .
---
paper_title: The Computational Complexity of Abduction

paper_content:

Abstract The problem of abduction can be characterized as finding the best explanation of a set of data. In this paper we focus on one type of abduction in which the best explanation is the most plausible combination of hypotheses that explains all the data. We then present several computational complexity results demonstrating that this type of abduction is intractable (NP-hard) in general. In particular, choosing between incompatible hypotheses, reasoning about cancellation effects among hypotheses, and satisfying the maximum plausibility requirement are major factors leading to intractability. We also identify a tractable, but restricted, class of abduction problems.
---
paper_title: The complexity of closed world reasoning and circumscription

paper_content:

Closed world reasoning is a common nonmonotonic technique that allows for dealing with negative information in knowledge and data bases. We present a detailed analysis of the computational complexity of the different forms of closed world reasoning for various fragments of propositional logic. The analysis allows us to draw a complete picture of the tractability/ intractability frontier for such a form of nonmonotonic reasoning. We also discuss how to use our results in order to characterize the computational complexity of other problems related to nonmonotonic inheritance, diagnosis, and default reasoning.
---
paper_title: Relating Default Logic and Circumscription

paper_content:

Default logic and the various forms of circumscription were developed to deal with similar problems. In this paper, we consider what is known about the relationships between the two approaches and present several new results extending this knowledge. We show that there are interesting cases in which the two formalisms do not correspond, as well as cases where default logic subsumes circumscription. We also consider positive and negative results on translating between defaults and circumscription, and develop a context in which they can be evaluated.
---
paper_title: What does a conditional knowledge base entail?

paper_content:

This paper presents a logical approach to nonmonotonic reasoning based on the notion of a nonmonotonic consequence relation. A conditional knowledge base, consisting of a set of conditional assertions of the type"if ... then ...", represents the explicit defeasible knowledge an agent has about the way the world generally behaves. We look for a plausible definition of the set of all conditional assertions entailed by a conditional knowledge base. In a previous paper, S. Kraus and the authors defined and studied"preferential"consequence relations. They noticed that not all preferential relations could be considered as reasonable inference procedures. This paper studies a more restricted class of consequence relations,"rational"relations. It is argued that any reasonable nonmonotonic inference procedure should define a rational relation. It is shown that the rational relations are exactly those that may be represented by a"ranked"preferential model, or by a (non-standard) probabilistic model. The rational closure of a conditional knowledge base is defined and shown to provide an attractive answer to the question of the title. Global properties of this closure operation are proved: it is a cumulative operation. It is also computationally tractable. This paper assumes the underlying language is propositional.
---

Title: A Survey on Complexity Results for Non-monotonic Logics

Section 1: Introduction
Description 1: This section provides an overview of non-monotonic logics and the motivation behind using default assumptions for more compact knowledge representation. It also outlines the paper's goals and mentions related work in the literature.

Section 2: Complexity Classes
Description 2: This section offers a brief overview of the complexity concepts and classes used throughout the paper, such as P, NP, co-NP, p_2, and the polynomial hierarchy.

Section 3: Default Logic
Description 3: This section discusses default logic, the main computational problems associated with it, and significant complexity results. It also covers various restrictions that lead to polynomials tractable cases.

Section 4: Modal Non-Monotonic Logics
Description 4: This section reviews complexity results concerning non-monotonic versions of modal logics, particularly focusing on autoepistemic logic and its variants.

Section 5: Negation in Logic Programming
Description 5: This section surveys the complexity results for various semantics for negation in logic programming, including stable model, well-founded, supported model, and other semantics.

Section 6: Inference
Description 6: This section addresses the complexity of inference for circumscription and closed-world reasoning and discusses classes of formulae whose circumscription is first-order.

Section 7: Satisfiability
Description 7: This section examines the complexity of determining the satisfiability of circumscription and extended closed world scenarios.

Section 8: Model Checking
Description 8: This section focuses on the problem of model checking in circumscription and proves the complexity results associated with different types of formulae.

Section 9: Model Finding
Description 9: This section discusses the complexity of finding satisfying assignments (models) for circumscriptive theories, with a particular focus on propositional logic.

Section 10: Abduction
Description 10: This section delves into the complexity of logic-based abduction, outlining various decision tasks and preference criteria that affect the complexity.

Section 11: Polynomial Reductions between NMR Problems
Description 11: This section explores polynomial transformations between different non-monotonic reasoning problems and explains their significance for complexity analysis.

Section 12: Conclusions
Description 12: This section summarizes the surveyed complexity results and discusses the implications for designing algorithms for non-monotonic reasoning, mentioning areas not covered in the paper.