Search

We survey a selection of inconsistency measures from the literature and investigate their computational complexity wrt. decision problems related to bounds on the inconsistency value and the functional problem of determining the actual value. Our findings show that those inconsistency measures can be partitioned into four classes related to their complexity. The first three classes contain measures whose complexities are located on the first three levels of the polynomial hierarchy, respectively. The final class is under standard complexity-theoretic assumptions located beyond the polynomial hierarchy. We provide membership results for all the investigated problems and completeness results for most of them. In addition, we undertake a preliminary study on the computational complexity of the measures on fragments of propositional logic.

A Abstract argumentation frameworks (AFs), originally proposed by Dung, constitute a central formal model for the study of computational aspects of argumentation in AI. Credulous and skeptical acceptance of arguments in a given AF are well-studied problems both in terms of theoretical analysis-especially computational complexity-and the development of practical decision procedures for the problems. However, AFs make the assumption that all attacks between arguments are certain (i.e., present attacks are known to exist, and missing attacks are known to not exist), which can in various settings be a restrictive assumption. A generalization of AFs to incomplete AFs was recently proposed as a formalism that allows the representation of both uncertain attacks and uncertain arguments in AFs. In this article, we explore the impact of allowing for modeling such uncertainties in AFs on the computational complexity of natural generalizations of acceptance problems to incomplete AFs under various central AF semantics. Complementing the complexity-theoretic analysis, we also develop the first practical decision procedures for all of the NP-hard variants of acceptance in incomplete AFs. In terms of complexity analysis, we establish a full complexity landscape, showing that depending on the variant of acceptance and property/semantics, the complexity of acceptance in incomplete AFs ranges from polynomial-time decidable to completeness for Sigma(p)(3). In terms of algorithms, we show through an extensive empirical evaluation that an implementation of the proposed decision procedures, based on boolean satisfiability (SAT) solving, is effective in deciding variants of acceptance under uncertainties. We also establish conditions for what type of atomic changes are guaranteed to be redundant from the perspective of preserving extensions of completions of incomplete AFs, and show that the results allow for considerably improving the empirical efficiency of the proposed SAT-based counterexample-guided abstraction refinement algorithms for acceptance in incomplete AFs for problem variants with complexity beyond NP. (C) 2021 The Authors. Published by Elsevier B.V.

Summarization: In many real-world settings, the structure of the environment constrains the formation of coalitions among agents. These settings can be represented by characteristic function games, also known as coalitional games, equipped with interaction graphs. An interaction graph determines the set of all feasible coalitions, in that a coalition C can form only if the subgraph induced over the nodes/agents in C is connected. Our work analyzes stability issues arising in such environments, by focusing on the core as a solution concept, and by considering the coalition structure viewpoint, that is, without assuming that the grand-coalition necessarily forms. The complexity of the coalition structure core is studied over a variety of interaction graph structures of interest, including complete graphs, lines, cycles, trees, and nearly-acyclic graphs (formally, having bounded treewidth). The related stability concepts of the least core and the cost of stability are also studied. Results are derived for the setting of compact coalitional games, i.e., for games that are implicitly described via a compact encoding, and where simple calculations on this encoding are to be performed in order to compute the payoff associated with any coalition. Moreover, specific results are provided for compact games defined via marginal contribution networks, an expressive encoding mechanism that received considerable attention in the last few years. Presented on: Artificial Intelligence

Causal graphs are widely used in planning to capture the internal structure of planning instances. Researchers have paid special attention to the subclass of planning instances with acyclic causal graphs, which in the past have been exploited to generate hierarchical plans, to compute heuristics, and to identify classes of planning instances that are easy to solve. This naturally raises the question of whether planning is easier when the causal graph is acyclic. In this article we show that the answer to this question is no, proving that in the worst case, the problem of plan existence is PSPACE-complete even when the causal graph is acyclic. Since the variables of the planning instances in our reduction are propositional, this result applies to Strips planning with negative preconditions. We show that the reduction still holds if we restrict actions to have at most two preconditions. Having established that planning is hard for acyclic causal graphs, we study two subclasses of planning instances with acyclic causal graphs. One such subclass is described by propositional variables that are either irreversible or symmetrically reversible. Another subclass is described by variables with strongly connected domain transition graphs. In both cases, plan existence is bounded away from PSPACE, but in the latter case, the problem of bounded plan existence is hard, implying that optimal planning is significantly harder than satisficing planning for this class.

The changing of arguments and their attack relation is an intrinsic property of a variety of argumentation systems. So, it is very important to efficiently figure out how the status of arguments in a system evolves when the system is updated. However, unlike other areas of argumentation that have been deeply explored, such as argumentation semantics, proof theories, and algorithms, etc., dynamics of argumentation systems has been comparatively neglected. In this paper, we formulate a general theory (called a division-based method) to cope with this problem based on a new concept: the division of an argumentation framework. When an argumentation framework is updated, it is divided into three parts: an unaffected, an affected, and a conditioning part. The status of arguments in the unaffected sub-framework remains unchanged, while the status of the affected arguments is computed in a special argumentation framework (called a conditioned argumentation framework, or briefly CAF) that is composed of an affected part and a conditioning part. We have proved that under a certain semantics that satisfies the directionality criterion (complete, preferred, ideal, or grounded semantics), the extensions of the updated framework are equal to the result of a combination of the extensions of an unaffected sub-framework and sets of the extensions of a set of assigned CAFs. Due to the efficiency of the division-based method, it is expected to be very useful in various kinds of argumentation systems where arguments and attacks are dynamics.

We consider how to combine the preferences of multiple agents despite the presence of incompleteness and incomparability in their preference relations over possible candidates. The set of preference relations of an agent may be incomplete because, for example, there is an ongoing preference elicitation process. There may also be incomparability as this is useful, for example, in multi-criteria scenarios. We focus here on the problem of computing the possible and necessary winners, that is, those candidates which can be, or always are, the most preferred for the agents. Possible and necessary winners are useful in many scenarios including preference elicitation. First, we show that testing possible and necessary winners is in general a computationally intractable problem for STV with unweighted votes and the cup rule with weighted votes, as is providing a good approximation of such sets. Then, we identify general properties of the preference aggregation function, such as independence to irrelevant alternatives, which are sufficient for such sets to be computed in polynomial time. Finally, we show how possible and necessary winners can be used to focus preference elicitation. We show that it is computationally intractable for the cup rule with weighted votes in the worst-case to decide when to terminate elicitation. However, we identify a property of the preference aggregation function that allows us to decide when to terminate elicitation in polynomial time, by focusing on possible and necessary winners.

The addition of aggregates has been one of the most relevant enhancements to the language of answer set programming (ASP). They strengthen the modelling power of ASP in terms of natural and concise problem representations. Previous semantic definitions typically agree in the case of non-recursive aggregates, but the picture is less clear for aggregates involved in recursion. Some proposals explicitly avoid recursive aggregates, most others differ, and many of them do not satisfy desirable criteria, such as minimality or coincidence with answer sets in the aggregate-free case.\ud \ud In this paper we define a semantics for programs with arbitrary aggregates (including monotone, antimonotone, and nonmonotone aggregates) in the full ASP language allowing also for disjunction in the head (disjunctive logic programming — DLP). This semantics is a genuine generalization of the answer set semantics for DLP, it is defined by a natural variant of the Gelfond–Lifschitz transformation, and treats aggregate and non-aggregate literals in a uniform way. This novel transformation is interesting per se also in the aggregate-free case, since it is simpler than the original transformation and does not need to differentiate between positive and negative literals. We prove that our semantics guarantees the minimality (and therefore the incomparability) of answer sets, and we demonstrate that it coincides with the standard answer set semantics on aggregate-free programs.\ud \ud Moreover, we carry out an in-depth study of the computational complexity of the language. The analysis pays particular attention to the impact of syntactical restrictions on programs in the form of limited use of aggregates, disjunction, and negation. While the addition of aggregates does not affect the complexity of the full DLP language, it turns out that their presence does increase the complexity of normal (i.e., non-disjunctive) ASP programs up to the second level of the polynomial hierarchy. However, we show that there are large classes of aggregates the addition of which does not cause any complexity gap even for normal programs, including the fragment allowing for arbitrary monotone, arbitrary antimonotone, and stratified (i.e., non-recursive) nonmonotone aggregates. The analysis provides some useful indications on the possibility to implement aggregates in existing reasoning engines.

We develop a formal framework for comparing different versions of ontologies, and apply it to ontologies formulated in terms of DL-Lite, a family of ‘lightweight’ description logics designed for data-intensive applications. The main feature of our approach is that we take into account the vocabulary (=signature) with respect to which one wants to compare ontologies. Five variants of difference and inseparability relations between ontologies are introduced and their respective applications for ontology development and maintenance discussed. These variants are obtained by generalising the notion of conservative extension from mathematical logic and by distinguishing between differences that can be observed among concept inclusions, answers to queries over ABoxes, by taking into account additional context ontologies, and by considering a model-theoretic, language-independent notion of difference. We compare these variants, study their meta-properties, determine the computational complexity of the corresponding reasoning tasks, and present decision algorithms. Moreover, we show that checking inseparability can be automated by means of encoding into QBF satisfiability and using off-the-shelf general purpose QBF solvers.Inseparability relations between ontologies are then used to develop a formal framework for (minimal) module extraction. We demonstrate that different types of minimal modules induced by these inseparability relations can be automatically extracted from real-world medium-size DL-Lite ontologies by composing the known tractable syntactic locality-based module extraction algorithm with our non-tractable extraction algorithms and using the multi-engine QBF solver aqme. Finally, we explore the relationship between uniform interpolation (or forgetting) and inseparability.

The Constraint Satisfaction Problem (CSP) is a central generic problem in artificial intelligence. Considerable progress has been made in identifying properties which ensure tractability in such problems, such as the property of being tree-structured. In this paper we introduce the broken-triangle property, which allows us to define a novel tractable class for this problem which significantly generalizes the class of problems with tree structure. We show that the broken-triangle property is conservative (i.e., it is preserved under domain reduction and hence under arc consistency operations) and that there is a polynomial-time algorithm to determine an ordering of the variables for which the broken-triangle property holds (or to determine that no such ordering exists). We also present a non-conservative extension of the broken-triangle property which is also sufficient to ensure tractability and can also be detected in polynomial time. We show that both the broken-triangle property and its extension can be used to eliminate variables, and that both of these properties provide the basis for preprocessing procedures that yield unique closures orthogonal to value elimination by enforcement of consistency. Finally, we also discuss the possibility of using the broken-triangle property in variable-ordering heuristics. © 2010 Elsevier B.V. All rights reserved.

We analyse the computational complexity of the recently proposed ideal semantics within both abstract argumentation frameworks (afs) and assumption-based argumentation frameworks (abfs). It is shown that while typically less tractable than credulous admissibi-lity semantics, the natural decision problems arising with this extension-based model can, perhaps surprisingly, be decided more efficiently than sceptical preferred semantics. In particular the task of finding the unique ideal extension is easier than that of deciding if a given argument is accepted under the sceptical semantics. We provide efficient algorithmic approaches for the class of bipartite argumentation frameworks and, finally, present a number of technical results which offer strong indications that typical problems in ideal argumentation are complete for the class p"@?^C of languages decidable by polynomial time algorithms allowed to make non-adaptive queries to a C oracle, where C is an upper bound on the computational complexity of deciding credulous acceptance: C=np for afs and logic programming (lp) instantiations of abfs; [email protected]"2^p for abfs modelling default theories.

The outcomes of many strategic situations such as parlor games or competitive economic scenarios are rankings of the participants, with higher ranks generally at least as desirable as lower ranks. Here we define ranking games as a class of n-player normal-form games with a payoff structure reflecting the players' von Neumann–Morgenstern preferences over their individual ranks. We investigate the computational complexity of a variety of common game-theoretic solution concepts in ranking games and deliver hardness results for iterated weak dominance and mixed Nash equilibrium when there are more than two players, and for pure Nash equilibrium when the number of players is unbounded but the game is described succinctly. This dashes hope that multi-player ranking games can be solved efficiently, despite their profound structural restrictions. Based on these findings, we provide matching upper and lower bounds for three comparative ratios, each of which relates two different solution concepts: the price of cautiousness, the mediation value, and the enforcement value.

We investigate the problem of coalitional manipulation in elections, which is known to be hard in a variety of voting rules. We put forward efficient algorithms for the problem in Borda, Maximin and Plurality with Runoff, and analyze their windows of error. Specifically, given an instance on which an algorithm fails, we bound the additional power the manipulators need in order to succeed. We finally discuss the implications of our results with respect to the popular approach of employing computational hardness to preclude manipulation.

Default logics are usually used to describe the regular behavior and normal properties of domain elements. In this paper we suggest, conversely, that the framework of default logics can be exploited for detecting outliers. Outliers are observations expressed by sets of literals that feature unexpected semantical characteristics. These sets of literals are selected among those explicitly embodied in the given knowledge base. Hence, essentially we perceive outlier detection as a knowledge discovery technique. This paper defines the notion of outlier in two related formalisms for specifying defaults: Reiter's default logic and extended disjunctive logic programs. For each of the two formalisms, we show that finding outliers is quite complex. Indeed, we prove that several versions of the outlier detection problem lie over the second level of the polynomial hierarchy. We believe that a thorough complexity analysis, as done here, is a useful preliminary step towards developing effective heuristics and exploring tractable subsets of outlier detection problems.

Evolutionary algorithms (EA) have been shown to be very effective in solving practical problems, yet many important theoretical issues of them are not clear. The expected first hitting time is one of the most important theoretical issues of evolutionary algorithms, since it implies the average computational time complexity. In this paper, we establish a bridge between the expected first hitting time and another important theoretical issue, i.e., convergence rate. Through this bridge, we propose a new general approach to estimating the expected first hitting time. Using this approach, we analyze EAs with different configurations, including three mutation operators, with/without population, a recombination operator and a time variant mutation operator, on a hard problem. The results show that the proposed approach is helpful for analyzing a broad range of evolutionary algorithms. Moreover, we give an explanation of what makes a problem hard to EAs, and based on the recognition, we prove the hardness of a general problem.

We propose a combination of logic programming under the answer set semantics with the description logics SHIF (D) and SHOIN (D), which underly the Web ontology languages OWL Lite and OWL DL, respectively. To this end, we introduce description logic programs (or dl-programs), which consist of a description logic knowledge base L and a finite set P of description logic rules (or dl-rules). Such rules are similar to usual rules in nonmonotonic logic programs, but they may also contain queries to L, possibly under default negation, in their bodies. They allow for building rules on top of ontologies but also, to a limited extent, building ontologies on top of rules. We define a suite of semantics for various classes of dl-programs, which conservatively extend the standard semantics of the respective classes and coincide with it in absence of a description logic knowledge base. More concretely, we generalize positive, stratified, and arbitrary normal logic programs to dl-programs, and define a Herbrand model semantics for them. We show that they have similar properties as ordinary logic programs, and also provide fixpoint characterizations in terms of (iterated) consequence operators. For arbitrary dl-programs, we define answer sets by generalizing Gelfond and Lifschitz's notion of a transform, leading to a strong and a weak answer set semantics, which are based on reductions to the semantics of positive dl-programs and ordinary positive logic programs, respectively. We also show how the weak answer sets can be computed utilizing answer sets of ordinary normal logic programs. Furthermore, we show how some advanced reasoning tasks for the Semantic Web, including different forms of closed-world reasoning and default reasoning, as well as DL-safe rules, can be realized on top of dl-programs. Finally, we give a precise picture of the computational complexity of dl-programs, and we describe efficient algorithms and a prototype implementation of dl-programs which is available on the Web. © 2008 Elsevier B.V. All rights reserved.

International audience; Abduction is a fundamental form of nonmonotonic reasoning that aims at finding explanations for observed manifestations. This process underlies many applications, from car configuration to medical diagnosis. We study here the computational complexity of deciding whether an explanation exists in the case when the application domain is described by a propositional knowledge base. Building on previous results, we classify the complexity for local restrictions on the knowledge base and under various restrictions on hypotheses and manifestations. In comparison to the many previous studies on the complexity of abduction we are able to give a much more detailed picture for the complexity of the basic problem of deciding the existence of an explanation. It turns out that depending on the restrictions, the problem in this framework is always polynomial-time solvable, NP-complete, coNP-complete, or Sigma_2P -complete. Based on these results, we give an a posteriori justification of what makes propositional abduction hard even for some classes of knowledge bases which allow for efficient satisfiability testing and deduction. This justification is very simple and intuitive, but it reveals that no nontrivial class of abduction problems is tractable. Indeed, tractability essentially requires that the language for knowledge bases is unable to express both causal links and conflicts between hypotheses. This generalizes a similar observation by Bylander et al. for set-covering abduction.

We report complexity results about redundancy of formulae in 2CNF form. We first consider the problem of checking redundancy and show some algorithms that are slightly better than the trivial one. We then analyze problems related to finding irredundant equivalent subsets (I.E.S.) of a given set. The concept of cyclicity proved to be relevant to the complexity of these problems. Some results about Horn formulae are also shown., Comment: Corrected figures on Theorem 10; added and modified some references

One difficulty that arises in abstract argument systems is that many natural questions regarding argument acceptability are, in general, computationally intractable having been classified as complete for classes such as np, co-np, and Π2p. In consequence, a number of researchers have considered methods for specialising the structure of such systems so as to identify classes for which efficient decision processes exist. In this paper the effect of a number of graph-theoretic restrictions is considered: k-partite systems (k⩾2) in which the set of arguments may be partitioned into k sets each of which is conflict-free; systems in which the numbers of attacks originating from and made upon any argument are bounded; planar systems; and, finally, those of k-bounded treewidth. For the class of bipartite graphs, it is shown that determining the acceptability status of a specific argument can be accomplished in polynomial-time under both credulous and sceptical semantics. In addition we establish the existence of polynomial time methods for systems having bounded treewidth when deciding the following: whether a given (set of) arguments is credulously accepted; if the system has a non-empty preferred extension; has a stable extension; is coherent; has at least one sceptically accepted argument. In contrast to these positive results, however, deciding whether an arbitrary set of arguments is “collectively acceptable” remains np-complete in bipartite systems. Furthermore for both planar and bounded degree systems the principal decision problems are as hard as the unrestricted cases. In deriving these latter results we introduce various concepts of “simulating” a general argument system by a restricted class so allowing any argument system to be translated to one which has both bounded degree and is planar. Finally, for the development of basic argument systems to so-called “value-based frameworks”, we present results indicating that decision problems known to be intractable in their most general form remain so even under quite severe graph-theoretic restrictions. In particular the problem of deciding “subjective acceptability” continues to be np-complete even when the underlying graph is a binary tree.

We study Coalitional Resource Games (crgs), a variation of Qualitative Coalitional Games (qcgs) in which each agent is endowed with a set of resources, and the ability of a coalition to bring about a set of goals depends on whether they are collectively endowed with the necessary resources. We investigate and classify the computational complexity of a number of natural decision problems for crgs, over and above those previously investigated for qcgs in general. For example, we show that the complexity of determining whether conflict is inevitable between two coalitions with respect to some stated resource bound (i.e., a limit value for every resource) is co-np-complete. We then investigate the relationship between crgs and qcgs, and in particular the extent to which it is possible to translate between the two models. We first characterise the complexity of determining equivalence between crgs and qcgs. We then show that it is always possible to translate any given crg into a succinct equivalent qcg, and that it is not always possible to translate a qcg into an equivalent crg; we establish some necessary and some sufficient conditions for a translation from qcgs to crgs to be possible, and show that even where an equivalent crg exists, it may have size exponential in the number of goals and agents of its source qcg.

We consider how to forget a set of atoms in a logic program. Intuitively, when a set of atoms is forgotten from a logic program, all atoms in the set should be eliminated from this program in some way, and other atoms related to them in the program might also be affected. We define notions of strong and weak forgettings in logic programs to capture such intuition, reveal their close connections to the notion of forgetting in classical propositional theories, and provide a precise semantic characterization for them. Based on these notions, we then develop a general framework for conflict solving in logic programs. We investigate various semantic properties and features in relation to strong and weak forgettings and conflict solving in the proposed framework. We argue that many important conflict solving problems can be represented within this framework. In particular, we show that all major logic program update approaches can be transformed into our framework, under which each approach becomes a specific conflict solving case with certain constraints. We also study essential computational properties of strong and weak forgettings and conflict solving in the framework.

The RCC8 constraint language developed by Randell et al. has been popularly adopted by the Qualitative Spatial Reasoning and GIS communities. The recent observation that RCC8 composition table describes only weak composition instead of composition raises questions about Renz and Nebel's maximality results about the computational complexity of reasoning with RCC8. This paper shows that any consistent RCC8 binary constraint network (RCC8 network for short) can be consistently extended. Given Θ, an RCC8 network, and z, a fresh variable, suppose xTy∈Θ and T is contained in the weak composition of R and S. This means that we can add two new constraints xRz and zSy to Θ without changing the consistency of the network. The result guarantees the applicability to RCC8 of one key technique, (Theorem 5) of [J. Renz, B. Nebel, On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus. Artificial Intelligence 108 (1999) 69-123], which allows the transfer of tractability of a set of RCC8 relations to its closure under composition, intersection, and converse. © 2005 Elsevier B.V. All rights reserved.

Many tasks require evaluating a specified Boolean expression @f over a set of probabilistic tests whose costs and success probabilities are each known. A strategy specifies when to perform which test, towards determining the overall outcome of @f. We are interested in finding the strategy with the minimum expected cost. As this task is typically NP-hard-for example, when tests can occur many times within @f, or when there are probabilistic correlations between the test outcomes-we consider those cases in which the tests are probabilistically independent and each appears only once in @f. In such cases, @f can be written as an and-or tree, where each internal node corresponds to either the ''and'' or ''or'' of its children, and each leaf node is a probabilistic test. In this paper we investigate ''probabilistic and-or tree resolution'' (PAOTR), namely the problem of finding optimal strategies for and-or trees. We first consider a depth-first approach: evaluate each penultimate rooted subtree in isolation, replace each such subtree with a single ''mega-test'', and recurse on the resulting reduced tree. We show that the strategies produced by this approach are optimal for and-or trees with depth at most two but can be arbitrarily sub-optimal for deeper trees. Each depth-first strategy can be described by giving the linear relative order in which tests are to be executed, with the understanding that any test whose outcome becomes irrelevant is skipped. The class of linear strategies is strictly larger than depth-first strategies. We show that even the best linear strategy can also be arbitrarily sub-optimal. We next prove that an optimal strategy honors a natural partial order among tests with a common parent node (''leaf-sibling tests''), and use this to produce a dynamic programming algorithm that finds the optimal strategy in time O(d^2(r+1)^d), where r is the maximum number of leaf-siblings and d is the number of leaf-parents; hence, for trees with a bounded number of internal nodes, this run-time is polynomial in the tree size. We also present another special class of and-or trees for which this task takes polynomial time. We close by presenting a number of other plausible approaches to PAOTR, together with counterexamples to show their limitations.

A fragment of English featuring temporal prepositions and the order-denoting adjectives first and last is defined by means of a context-free grammar. The phrase-structures which this grammar assigns to the sentences it recognizes are viewed as formulas of an interval temporal logic, whose satisfaction-conditions faithfully represent the meanings of the corresponding English sentences. It is shown that the satisfiability problem for this logic is NEXPTIME-complete. The computational complexity of determining logical relationships between English sentences featuring the temporal constructions in question is thus established.

The use of software agents for automatic contract negotiation in e-commerce and e-trading environments has been the subject of considerable recent interest. A widely studied abstract model considers the setting in which a set of agents have some collection of resources shared out between them and attempt to construct a mutually beneficial optimal reallocation of these by trading resources. The simplest such trades are those in which a single agent transfers exactly one resource to another—so-called ‘one-resource-at-a-time’ or ‘O-contracts’. In this research note we consider the computational complexity of a number of natural decision problems in this setting.

We study coalitional games in which agents are each assumed to have a goal to be achieved, and where the characteristic property of a coalition is a set of choices , with each choice denoting a set of goals that would be achieved if the choice was made. Such qualitative coalitional games ( qcg s) are a natural tool for modelling goal-oriented multiagent systems. After introducing and formally defining qcg s, we systematically formulate fourteen natural decision problems associated with them, and determine the computational complexity of these problems. For example, we formulate a notion of coalitional stability inspired by that of the core from conventional coalitional games, and prove that the problem of showing that the core of a qcg is non-empty is D p 1 -complete. (As an aside, we present what we believe is the first “natural” problem that is proven to be complete for D p 2 .) We conclude by discussing the relationship of our work to other research on coalitional reasoning in multiagent systems, and present some avenues for future research.

A new framework for propositional merging is presented. DA2 merging operators, parameterized by a distance between interpretations and two aggregation functions, are introduced. Many distances and aggregation functions can be used and many merging operators already defined in the literature (including both model-based ones and syntax-based ones) can be encoded as specific DA2 operators. Both logical and complexity properties of those operators are studied. An important result is that (under very weak assumptions) query entailment from merged bases is “only” at the first level of the polynomial hierarchy when any of the DA2 operators is used. As a by-product, complexity results for several existing merging operators are derived as well.

Andréka and Maddux [Notre Dame J. Formal Logic 35 (4) 1994] classified the small relation algebras—those with at most 8 elements, or in other terms, at most 3 atomic relations. They showed that there are eighteen isomorphism types of small relation algebras, all representable. For each simple, small relation algebra they computed the spectrum of the algebra, namely the set of cardinalities of square representations of that relation algebra.In this paper we analyze the computational complexity of the problem of deciding the satisfiability of a finite set of constraints built on any small relation algebra. We give a complete classification of the complexities of the general constraint satisfaction problem for small relation algebras. For three of the small relation algebras the constraint satisfaction problem is NP-complete, for the other fifteen small relation algebras the constraint satisfaction problem has cubic (or lower) complexity.We also classify the complexity of the constraint satisfaction problem over fixed finite representations of any relation algebra. If the representation has size two or less then the complexity is cubic (or lower), but if the representation is square, finite and bigger than two then the complexity is NP-complete.

We completely classify the computational complexity of the basic achievement and maintenance agent design problems in bounded environments when these problems are parameterized by the number of environment states and the number of agent actions. The different problems are P-complete, NP-complete, co-NP-complete or PSPACE-complete (when they are not trivial). We also consider alternative achievement and maintenance agent design problems by allowing longer runs in environments (that is, our environments are bounded but the bounds are more liberal than was the case previously). Again, we obtain a complete classification but so that the different problems are DEXPTIME-complete, NEXPTIME-complete, co-NEXPTIME-complete or NEXPSPACE-complete (when they are not trivial).

Argument Systems provide a rich abstraction within which divers concepts of reasoning, acceptability and defeasibility of arguments, etc., may be studied using a unified framework. Two important concepts of the acceptability of an argument p in such systems are credulous acceptance to capture the notion that pcan be ‘believed’; and sceptical acceptance capturing the idea that if anything is believed, then pmust be. One important aspect affecting the computational complexity of these problems concerns whether the admissibility of an argument is defined with respect to ‘preferred’ or ‘stable’ semantics. One benefit of so-called ‘coherent’ argument systems being that the preferred extensions coincide with stable extensions. In this note we consider complexity-theoretic issues regarding deciding if finitely presented argument systems modelled as directed graphs are coherent. Our main result shows that the related decision problem is Π2(p)-complete and is obtained solely via the graph-theoretic representation of an argument system, thus independent of the specific logic underpinning the reasoning theory.

Bondarenko et al. have recently proposed an abstract framework for default reasoning. Besides capturing most existing formalisms and proving that their standard semantics all coincide, the framework extends these formalisms by generalising the semantics of admissible and preferred arguments, originally proposed for logic programming only. In this paper we analyse the computational complexity of credulous and sceptical reasoning under the semantics of admissible and preferred arguments for (the propositional variant of) the instances of the abstract framework capturing theorist, circumscription, logic programming, default logic, and autoepistemic logic. Although the new semantics have been tacitly assumed to mitigate the computational hardness of default reasoning under the standard semantics of stable extensions, we show that in many cases reasoning under the admissibility and preferability semantics is computationally harder than under the standard semantics. In particular, in the case of autoepistemic logic, sceptical reasoning under preferred arguments is located at the fourth level of the polynomial hierarchy, whereas the same form of reasoning under stable extensions is located at the second level. © 2002 Elsevier Science B.V. All rights reserved. 141 1-2 57 78 Cited By :54

Information about the size of spatial regions is often easily accessible and, when combined with other types of spatial information, it can be practically very useful. In this paper we introduce four classes of qualitative and metric size constraints, and we study their integration with the Region Connection Calculus RCC-8, a well-known approach to qualitative spatial reasoning with topological relations. We propose a new path-consistency algorithm for combining RCC-8 relations and qualitative size relations. The algorithm is complete for deciding satisfiability of an input set of topological constraints over one of the three maximal tractable subclasses of RCC-8 containing all the basic relations. Moreover, its time complexity is cubic and is the same as the complexity of the best-known method for deciding satisfiability when only these topological relations are considered. We also provide results on finding a consistent scenario in cubic time for these combined classes.Regarding metric size constraints, we first study their combination with RCC-8 and we show that deciding satisfiability for the combined sets of constraints is NP-hard, even when only the RCC-8 basic relations are used. Then we introduce RCC-7, a subalgebra of RCC-8 that can be used for applications where spatial regions cannot partially overlap. We show that reasoning with the seven RCC-7 basic relations and the universal relation is intractable, but that reasoning with the RCC-7 basic relations combined with metric size information is tractable. Finally, we give a polynomial algorithm for the latter case and a backtracking algorithm for the general case.

This paper studies functional dependencies in q-Horn theories, and discusses their use in knowledge condensation. We introduce compact model-based representations of q-Horn theories, analyze the structure of functional dependencies in q-Horn theories, and show that every minimal functional dependency in a q-Horn theory Σ can be expressed either by a single term or by a single clause. We also prove that the set of all minimal functional dependencies in Σ is quasi-acyclic. We then develop polynomial time algorithms for recognizing whether a given functional dependency holds in a q-Horn theory, which is represented either by a q-Horn CNF or as the q-Horn envelope of a set of models. Finally, we show that every q-Horn theory has a unique condensation, and can be condensed in polynomial time.

In the last several years, there have been several studies about the computational complexity of classical planning assuming that the planner has complete knowledge about the initial situation. Recently, there have been proposals to use `sensing' actions to plan in the presence of incompleteness. In this paper we study the complexity of planning in such cases. In our study we use the action description language A proposed in 1991 by Gelfond and Lifschitz, and its extensions. It is known that if we consider only plans of tractable (polynomial) duration, planning in A —with complete information about the initial situation—is NP -complete: even checking whether a given objective is attainable from a given initial state is NP -complete. In this paper, we show that the planning problem in the presence of incompleteness is indeed harder: it belongs to the next level of the complexity hierarchy (in precise terms, it is Σ 2 P -complete). To overcome the complexity of this problem, Baral and Son have proposed several approximations. We show that under certain conditions, one of these approximations—0-approximation—makes the problem NP -complete (thus indeed reducing its complexity).

Belief revision and belief update are two different forms of belief change, and they serve different purposes. In this paper we focus on belief update, the formalization of change in beliefs due to changes in the world. The complexity of the basic update (introduced by Winslett, 1990) has been determined by Eiter and Gottlob (1992). Since then, many other formalizations have been proposed to overcome the limitations and drawbacks of Winslett's update. In this paper we analyze the complexity of the proposals presented in the literature: the standard semantics by Winslett (1986), the minimal change with exception and the minimal change with maximal disjunctive information by Zhang and Foo (1996), the update with disjunctive function by Herzig (1996), the abduction-based update and the generalized update by Boutilier (1996). We relate some of these approaches to belief update to previous work on closed world reasoning.

Although many formalisms for reasoning about action exist, surprisingly few approaches have taken computational complexity into consideration. The contributions of this article are the following: a temporal logic with a restriction for which deciding satisfiability is tractable, a tractable extension for reasoning about action, and NP-completeness results for the unrestricted problems. Many interesting reasoning problems can be modelled, involving nondeterminism, concurrency and memory of actions. The reasoning process is proved to be sound and complete.

In Part I of this series of papers, we developed a language called Agent Programs for defining the operational behavior of software agents and defined a set of successively more satisfying (epistemically) semantics for such agent programs. In Part II of this series of papers, we study the computation price to be paid (in terms of complexity) for these epistemic desiderata. In particular, we develop algorithms for the above semantics, and describe results on their computational complexity. We show that (surprisingly) the reasonable status set semantics is the easiest to compute of the semantics proposed.

The computational properties of qualitative spatial reasoning have been investigated to some degree. However, the question of the boundary between polynomial and NP-hard reasoning problems has not been addressed yet. In this paper we explore this boundary in the “Region Connection Calculus” RCC-8. We extend Bennett's encoding of RCC-8 in modal logic. Based on this encoding, we prove that reasoning is NP-complete in general and identify a maximal tractable subset of the relations in RCC-8 that contains all base relations. Further, we show that for this subset path-consistency is sufficient for deciding consistency.

We characterise the set of subalgebras of Allen's algebra which have a tractable satisfiability problem, and in addition contain certain basic relations. The conclusion is that no tractable subalgebra dial is not known in the literature can contain more than the three basic relations (≡), (b) and ( b⪰ ), where bϵd, o, s, f. This means that concerning algebras for specifying complete knowledge about temporal information, there is no hope of finding yet unknown classes with much expressivity. We also classify completely some cases where we cannot even express complete information (but close to complete), showing that there are exactly two maximal tractable algebras containing the relation (≺ ≻), exactly two containing the relation (≺ ≻ m m≤), and exactly three containing the relation (≺ m). The algebras containing (≺ ≻) can express the notion of sequentiality; thus we have a complete characterization of tractable inference using that notion.

Several results have been obtained in the past about the complexity of understanding line drawings of polyhedral scenes. Kirousis and Papadimitriou (1988) have shown that the problem of labeling line drawings of trihedral scenes is NP-complete. The human brain, however, seems to grasp at a glance the 3D structure associated with a line drawing. A possible explanation of this discrepancy, offered by Kirousis and Papadimitriou themselves, is that the worst-case complexity does not reflect the real difficulty of labeling line drawings, which might be far less in the average or in “typical” cases. However, no statistical analysis has ever been carried out to test this conjecture. The core of this paper is an algorithm for the generation of random instances of polyhedral scenes. Random instances of line drawings are then obtained as perspective projections of these scenes, and can be used as an input to standard labeling algorithms so as to derive experimental estimates of the complexity of these algorithms. The results indicate that the median-case complexity is linear in the number of junctions. This substantiates the conjecture that “typical” instances of line drawings are easy to label, and may help explain the ease by which the brain is able to solve the problem.

Nonmonotonic formalisms and belief revision operators have been introduced as useful tools to describe and reason about evolving scenarios. Both approaches have been proven effective in a number of different situations. However, little is known about their relationship. Previous work by Winslett has shown some correlations between a specific operator and circumscription. In this paper we greatly extend Winslett's work by establishing new relations between circumscription and a large number of belief revision operators. This highlights similarities and differences between these formalisms. Furthermore, these connections provide us with the possibility of importing results in one field into the other one.

This paper continues Nebel and Burckert's investigation of Allen's interval algebra by presenting nine more maximal tractable subclasses of the algebra (provided that P ≠ NP), in addition to their previously reported ORD-Horn subclass. Furthermore, twelve tractable subclasses are identified, whose maximality is not decided. Four of them can express the notion of sequentiality between intervals, which is not possible in the ORD-Horn algebra. All of the algebras are considerably larger than the ORD-Horn subclass. The satisfiability algorithm, which is common for all the algebras, is shown to be linear. Furthermore, the path consistency algorithm is shown to decide satisfiability of interval networks using any of the algebras.

The constraint satisfaction problem (CSP) is a central generic problem in computer science and artificial intelligence: it provides a common framework for many theoretical problems as well as for many real-life applications. Valued constraint problems are a generalisation of the CSP which allow the user to model optimisation problems. Considerable effort has been made in identifying properties which ensure tractability in such problems. In this work, we initiate the study of hybrid tractability of valued constraint problems; that is, properties which guarantee tractability of the given valued constraint problem, but which do not depend only on the underlying structure of the instance (such as being tree-structured) or only on the types of valued constraints in the instance (such as submodularity). We present several novel hybrid classes of valued constraint problems in which all unary constraints are allowed, which include a machine scheduling problem, constraint problems of arbitrary arities with no overlapping nogoods, and the SoftAllDiff constraint with arbitrary unary valued constraints. An important tool in our investigation will be the notion of forbidden substructures.

We present an approach where probabilistic logic is combined with default reasoning from conditional knowledge bases in Kraus et al.'s System P, Pearl's System Z, and Lehmann's lexicographic entailment. The resulting probabilistic generalizations of default reasoning from conditional knowledge bases allow for handling in a uniform framework strict logical knowledge, default logical knowledge, as well as purely probabilistic knowledge. Interestingly, probabilistic entailment in System P coincides with probabilistic entailment under g-coherence from imprecise probability assessments. We then analyze the semantic and nonmonotonic properties of the new formalisms. It turns out that they all are proper generalizations of their classical counterparts and have similar properties as them. In particular, they all satisfy the rationality postulates of System P and some Direct Inference property. Moreover, probabilistic entailment in System Z and probabilistic lexicographic entailment both satisfy the property of Rational Monotonicity and some Irrelevance property, while probabilistic entailment in System P does not. We also analyze the relationships between the new formalisms. Here, probabilistic entailment in System P is weaker than probabilistic entailment in System Z, which in turn is weaker than probabilistic lexicographic entailment. Moreover, they all are weaker than entailment in probabilistic logic where default sentences are interpreted as strict sentences. Under natural conditions, probabilistic entailment in System Z and lexicographic entailment even coincide with such entailment in probabilistic logic, while probabilistic entailment in System P does not. Finally, we also present algorithms for reasoning under probabilistic entailment in System Z and probabilistic lexicographic entailment, and we give a precise picture of its complexity.