1,721,014 research outputs found
Complexity results on DPLL and resolution
No full textDPLL and resolution are two popular methods for solving the problem of propositional satisfiability. Rather than algorithms, they are families of algorithms, as their behavior depends on some choices they face during execution: DPLL depends on the choice of the literal to branch on; resolution depends on the choice of the pair of clauses to resolve at each step. The complexity of making the optimal choice is analyzed in this article. Extending previous results, we prove that choosing the optimal literal to branch on in DPLL is Delta(p)(2)[logn]-hard, and becomes NPPP-hard if branching is only allowed on a subset of variables. Optimal choice in regular resolution is both NP-hard and coNP-hard. The problem of determining the size of the optimal proofs is also analyzed: it is coNP-hard for DPLL, and Delta(p)(2)[logn]-hard if a conjecture we make is true. This problem is coNP-hard for regular resolution
On the complexity of extension checking in default logic
No full textThe complexity of deciding equivalence of a formula to an extension of a default theory is investigated for the Reiter, justified, constrained, and rational semantics. (c) 2005 Elsevier B.V. All rights reserved
Representing states in iterated belief revision
Full text linkIterated belief revision requires information about the current beliefs. This information is represented by mathematical structures called doxastic states. Most literature concentrates on how to revise a doxastic state and neglects that it may exponentially grow. This problem is studied for the most common ways of storing a doxastic state. All four of them are able to store every doxastic state, but some do it in less space than others. In particular, the explicit representation (an enumeration of the current beliefs) is the more wasteful on space. The level representation (a sequence of propositional formulae) and the natural representation (a history of natural revisions) are more succinct than it. The lexicographic representation (a history of lexicographic revision) is even more succinct than them
Representability in default logic
No full textA default theory can be seen as a way for representing a set of formulae, i.e., its extensions. In this paper, we characterize the sets of formulae that can be expressed by a default theory according to various semantics: justified, constrained, rational, cumulative, QDL, CADL, and two semantics with priorities. These characterizations imply some non-translatability results between semantics
On polynomial sized MDP succinct policies
No full textPolicies of Markov Decision Processes (MDPs) determine the next action to execute from the current state and, possibly, the history (the past states). When the number of states is large, succinct representations are often used to compactly represent both the MDPs and the policies in a reduced amount of space. In this paper, some problems related to the size of succinctly represented policies are analyzed. Namely, it is shown that some MDPs have policies that can only be represented in space super-polynomial in the size of the MDP, unless the polynomial hierarchy collapses. This fact motivates the study of the problem of deciding whether a given MDP has a policy of a given size and reward. Since some algorithms for MDPs work by finding a succinct representation of the value function, the problem of deciding the existence of a succinct representation of a value function of a given size and reward is also considered
Where fail-safe default logics fail
No full textReiter's original definition of default logic allows for the application of a default that contradicts a previously applied one. We call this condition failure. The possibility of generating failures has been in the past considered as a semantical problem, and variants have been proposed to solve it. We show that it is instead a computational feature that is needed to encode some domains into default logic
Belief Integration and Source Reliability Assessment
Full text linkMerging beliefs requires the plausibility of the sources of the information to be merged. They are typically assumed equally reliable when nothing suggests otherwise. A recent line of research has spun from the idea of deriving this information from the revision process itself. In particular, the history of previous revisions and previous merging examples provide information for performing subsequent merging operations.
Yet, no examples or previous revisions may be available. In spite of the apparent lack of information, something can still be inferred by a try-and-check approach: a relative reliability ordering is assumed, the sources are integrated according to it and the result is compared with the original information. The final check may contradict the original ordering, like when the result of merging implies the negation of a formula coming from a source initially assumed reliable, or it implies a formula coming from a source assumed unreliable. In such cases, the reliability ordering assumed in the first place can be excluded from consideration.
Such a scenario is proved real under the classifications of source reliability and definitions of belief integration considered in this article: sources divided in two, three or multiple reliability classes; integration is mostly by maximal consistent subsets but also weighted distance is considered. Other results mainly concern the integration by maximal consistent subsets and partitions of two and three reliability classes
Seminormalizing a default theory
No full textMost of the work in default logic is about default theories that are completely specified. In this category are the proposals of appropriate semantics for default logic, the characterizations of the complexity of reasoning with a default theory, the algorithms for finding consequences of default theories, etc. Relatively little attention has been paid to the process of building a default theory, and most of the work on this topic is about translating knowledge bases from other formalisms (such as circumscription, autoepistemic logic, and action description languages) into default logic. This paper is about expressing knowledge in default logic. In particular, we assume that defaults are initially formulated as normal, and are then corrected using specific inference examples
Monotonic reductions, representative equivalence, and compilation of intractable problems
No full textThe idea of preprocessing pail of the input of a problem in order to improve efficiency has been employed by several researchers in several areas of computer science. In this article, we show sufficient conditions to prove that an intractable problem cannot be efficiently solved even allowing an exponentially long preprocessing phase. The generality of such conditions is shown by applying them to various problems coming from different fields. While the results may seem to discourage the use of compilation, we present some evidence that such negative results are useful in practice
- …
