Many real-world planning problems are oversubscription problems where all goals are not simultaneously achievable and the planner needs to find a feasible subset. We present complexity results for the so-called partial satisfaction and net benefit problems under various restrictions; this extends previous work by van den Briel et al. Our results reveal strong connections between these problems and with classical planning. We also present a method for efficiently compiling oversubscription problems into the ordinary plan existence problem; this can be viewed as a continuation of earlier work by Keyder and Geffner.
Causal graphs are widely used to analyze the complexity of planning problems. Many tractable classes have been identified with their aid and state-of-the-art heuristics have been derived by exploiting such classes. In particular, Katz and Keyder have studied causal graphs that are hourglasses (which is a generalization of forks and inverted-forks) and shown that the corresponding cost-optimal planning problem is tractable under certain restrictions. We continue this work by studying polytrees (which is a generalization of hourglasses) under similar restrictions. We prove tractability of cost-optimal planning by providing an algorithm based on a novel notion of variable isomorphism. Our algorithm also sheds light on the k-consistency procedure for identifying unsolvable planning instances. We speculate that this may, at least partially, explain why merge-and-shrink heuristics have been successful for recognizing unsolvable instances.
We present a quantum algorithm for finite domain constraint solving, where the constraints have arity 2. It is complete and runs in time, where d is size of the domain of the variables and n the number of variables. For the case of d=3 we provide a method to obtain an upper time bound of . Also for d=5 the upper bound has been improved. Using this method in a slightly different way we can decide 3-colourability in O(1.2185^n) time.
Counting the number of solutions to CSP instances has vast applications in several areas ranging from statistical physics to artificial intelligence. We provide a new algorithm for counting the number of solutions to binary CSP s which has a time complexity ranging from O ((d/4 . alpha(4))(n)) to O((alpha + alpha(5) + [d/4 - 1] . alpha(4))(n)) (where alpha approximate to 1.2561) depending on the domain size d greater than or equal to 3. This is substantially faster than previous algorithms, especially for small d. We also provide an algorithm for counting k-colourings in graphs and its running time ranges from O ([log(2) k](n)) to O ([log(2) k + 1](n)) depending on k greater than or equal to 4. Previously, only an O(1.8171(n)) time algorithm for counting 3-colourings were known, and we improve this upper bound to O(1.7879(n)).
Counting the number of solutions to CSP instances has applications in several areas, ranging from statistical physics to artificial intelligence. We give an algorithm for counting the number of solutions to binary CSPs, which works by transforming the problem into a number of 2-SAT instances, where the total number of solutions to these instances is the same as those of the original problem. The algorithm consists of two main cases, depending on whether the domain size d is even, in which case the algorithm runs in O(1.3247^n*(d/2)^n) time, or odd, in which case it runs in O(1.3247^n*((d^2+d+2)/4)^(n/2)) if d=4*k+1, and O(1.3247^n*((d^2+d)/4)^(n/2)) if d=4*k+3. We also give an algorithm for counting the number of possible 3-colourings of a given graph, which runs in O(1.8171^n), an improvement over our general algorithm gained by using problem specific knowledge.
The class of constraint satisfaction problems (CSPs) over finite domains has been shown to be NP-complete, but many tractable subclasses have been identified in the literature. In this paper we are interested in restrictions on the types of constraint relations in CSP instances. By a result of Jeavons et al. we know that a key to the complexity of classes arising from such restrictions is the closure properties of the sets of relations. It has been shown that sets of relations that are closed under constant, majority, affine, or associative, commutative, and idempotent (ACI) functions yield tractable subclasses of CSP. However, it has been unknown whether other closure properties may generate tractable subclasses. In this paper we introduce a class of tractable (in fact, SL-complete) CSPs based on bipartite graphs. We show that there are members of this class that are not closed under constant, majority, affine, or ACI functions, and that it, therefore, is incomparable with previously identified classes.
We systematically study the computational complexity of a broad class of computational problemsin phylogenetic reconstruction. The class contains for example the rooted triple consistencyproblem, forbidden subtree problems, the quartet consistency problem, and many other problemsstudied in the bioinformatics literature. The studied problems can be described as constraintsatisfaction problems where the constraints have a first-order definition over the rooted triplerelation. We show that every such phylogeny problem can be solved in polynomial time or isNP-complete. On the algorithmic side, we generalize a well-known polynomial-time algorithmof Aho, Sagiv, Szymanski, and Ullman for the rooted triple consistency problem. Our algorithmrepeatedly solves linear equation systems to construct a solution in polynomial time. We thenshow that every phylogeny problem that cannot be solved by our algorithm is NP-complete. Ourclassification establishes a dichotomy for a large class of infinite structures that we believe is ofindependent interest in universal algebra, model theory, and topology. The proof of our mainresult combines results and techniques from various research areas: a recent classification of themodel-complete cores of the reducts of the homogeneous binary branching C-relation, Leeb’sRamsey theorem for rooted trees, and universal algebra.
Let \Gamma be a structure with a finite relational signature and a first-order definition in (R;*,+) with parameters from R, that is, a relational structure over the real numbers where all relations are semi-algebraic sets. In this article, we study the computational complexity of constraint satisfaction problem (CSP) for \Gamma: the problem to decide whether a given primitive positive sentence is true in \Gamma. We focus on those structures \Gamma that contain the relations \leq, {(x,y,z) | x+y=z} and {1}. Hence, all CSPs studied in this article are at least as expressive as the feasibility problem for linear programs. The central concept in our investigation is essential convexity: a relation S is essentially convex if for all a,b\inS, there are only finitely many points on the line segment between a and b that are not in S. If \Gamma contains a relation S that is not essentially convex and this is witnessed by rational points a,b, then we show that the CSP for \Gamma is NP-hard. Furthermore, we characterize essentially convex relations in logical terms. This different view may open up new ways for identifying tractable classes of semi-algebraic CSPs. For instance, we show that if \Gamma is a first-order expansion of (R;*,+), then the CSP for \Gamma can be solved in polynomial time if and only if all relations in \Gamma are essentially convex (unless P=NP).
We study techniques for deciding the computational complexity of infinite-domain constraint satisfaction problems. For certain fundamental algebraic structures Delta, we prove definability dichotomy theorems of the following form: for every first-order expansion Gamma of Delta, either Gamma has a quantifier-free Horn definition in Delta, or there is an element d of Gamma such that all non-empty relations in Gamma contain a tuple of the form (d,...,d), or all relations with a first-order definition in Delta have a primitive positive definition in Gamma. The results imply that several families of constraint satisfaction problems exhibit a complexity dichotomy: the problems are in P or NP-hard, depending on the choice of the allowed relations. As concrete examples, we investigate fundamental algebraic constraint satisfaction problems. The first class consists of all first-order expansions of (Q;+). The second class is the affine variant of the first class. In both cases, we obtain full dichotomies by utilising our general methods.
We study logical techniques for deciding the computational complexity of infinite-domain constraint satisfaction problems (CSPs). For the fundamental algebraic structure where are the real numbers and L _{1},L _{2},... is an enumeration of all linear relations with rational coefficients, we prove that a semilinear relation R (i.e., a relation that is first-order definable with linear inequalities) either has a quantifier-free Horn definition in Γ or the CSP for is NP-hard. The result implies a complexity dichotomy for all constraint languages that are first-order expansions of Γ: the corresponding CSPs are either in P or are NP-complete depending on the choice of allowed relations. We apply this result to two concrete examples (generalised linear programming and metric temporal reasoning) and obtain full complexity dichotomies in both cases.
We investigate the computational complexity of temporal reasoning in different time models such as totally-ordered, partially-ordered and branching time. Our main result concerns the satisfiability problem for point algebras and point algebras extended with disjunctions—for these problems, we identify all tractable subclasses. We also provide a number of additional results; for instance, we present a new time model suitable for reasoning about systems with a bounded number of unsynchronized clocks, we investigate connections with spatial reasoning and we present improved algorithms for deciding satisfiability of the tractable point algebras.
Efficient reasoning about temporal constraints over nonlinear time models is vital in numerous application areas, such as planning, distributed systems and cooperating agents. We identify all tractable subclasses of the point algebra for partially-ordered time and examine one large, nontrivial tractable subclass of the point algebra for branching time.
An important question in constraint satisfaction is how to restrict the problem to ensure tractability (since the general problem is NP-hard). The use of disjunctions has proven to be a useful method for constructing tractable constraint classes from existing classes; the well-known ‘max-closed’ and ‘ORD-Horn’ constraints are examples of tractable classes that can be constructed this way. Three sufficient conditions (the guaranteed satisfaction property, 1-independence and 2-independence) that each ensure the tractability of constraints combined by disjunctions have been proposed in the literature. We show that these conditions are both necessary and sufficient for tractability in three different natural classes of disjunctive constraints. This suggests that deciding this kind of property is a very important task when dealing with disjunctive constraints. We provide a simple, automatic method for checking the 1-independence property—this method is applicable whenever the consistency of the constraints under consideration can be decided by path-consistency. Our method builds on a connection between independence and refinements (which is a way of reducing one constraint satisfaction problem to another.)
The early classifications of the computational complexity of planning under various restrictions in STRIPS (Bylander) and SAS+ (B¨ackstr¨om and Nebel) have influenced following research in planning in many ways. We go back and reanalyse their subclasses, but this time using the more modern tool of parameterized complexity analysis. This provides new results that together with the old results give a more detailed picture of the complexity landscape. We demonstrate separation results not possible with standard complexity theory, which contributes to explaining why certain cases of planning haveseemed simpler in practice than theory has predicted. In particular, we show that certain restrictions of practical interest are tractable in the parameterized sense of the term, and that a simple heuristic is sufficient to make a well-known partialorder planner exploit this fact.
Macros have long been used in planning to represent subsequences of operators. Macros can be used in place of individual operators during search, sometimes reducing the effort required to find a plan to the goal. Another use of macros is to compactly represent long plans. In this paper we introduce a novel solution concept called automaton plans in which plans are represented using hierarchies of automata. Automaton plans can be viewed as an extension of macros that enables parameterization and branching. We provide several examples that illustrate how automaton plans can be useful, both as a compact representation of exponentially long plans and as an alternative to sequential solutions in benchmark domains such as LOGISTICS and GRID. We also compare automaton plans to other compact plan representations from the literature, and find that automaton plans are strictly more expressive than macros, but strictly less expressive than HTNs and certain representations allowing efficient sequential access to the operators of the plan.
Macros have a long-standing role in planning as a tool for representing repeating subsequences of operators. Macros are useful both for guiding search towards a solution and for representing plans compactly. In this paper we introduce automata plans which consist of hierarchies of finite state automata. Automata plans can be viewed as an extension of macros that enables parametrization and branching. We provide several examples of the utility of automata plans, and prove that automata plans are strictly more expressive than macro plans. We also prove that automata plans admit polynomialtime sequential access of the operators in the underlying “flat” plan, and identify a subset of automata plans that admit polynomial-time random access. Finally, we compare automata plans with other representations allowing polynomial-time sequential access.
The use and study of compact representations of objects is widespread in computer science. AI planning can be viewed as the problem of finding a path in a graph that is implicitly described by a compact representation in a planning language. However, compact representations of the path itself (the plan) have not received much attention in the literature. Although both macro plans and reactive plans can be considered as such compact representations, little emphasis has been placed on this aspect in earlier work. There are also compact plan representations that are defined by their access properties, for instance, that they have efficient random access or efficient sequential access. We formally compare two such concepts with macro plans and reactive plans, viewed as compact representations, and provide a complete map of the relationships between them.
The causal graph of a planning instance is an important tool for planning both in practice and in theory. The theoretical studies of causal graphs have largely analysed the computational complexity of planning for instances where the causal graph has a certain structure, often in combination with other parameters like the domain size of the variables. Chen and Giménez ignored even the structure and considered only the size of the weakly connected components. They proved that planning is tractable if the components are bounded by a constant and otherwise intractable. Their intractability result was, however, conditioned by an assumption from parameterised complexity theory that has no known useful relationship with the standard complexity classes. We approach the same problem from the perspective of standard complexity classes, and prove that planning is NP-hard for classes with unbounded components under an additional restriction we refer to as SP-closed. We then argue that most NP-hardness theorems for causal graphs are difficult to apply and, thus, prove a more general result; even if the component sizes grow slowly and the class is not densely populated with graphs, planning still cannot be tractable unless the polynomial hierachy collapses. Both these results still hold when restricted to the class of acyclic causal graphs. We finally give a partial characterization of the borderline between NP-hard and NP-intermediate classes, giving further insight into the problem.
Modelling abstraction as a function from the original state space to an abstract state space is a common approach in combinatorial search. Sometimes this is too restricted, though, and we have previously proposed a framework using a more flexible concept of transformations between labelled graphs. We also proposed a number of properties to describe and classify such transformations. This framework enabled the modelling of a number of different abstraction methods in a way that facilitated comparative analyses. It is of particular interest that these properties can be used to capture the concept of refinement without backtracking between levels; how to do this has been an open question for at least twenty years. In this paper, we continue our previous research by analysing the complexity of testing the various transformation properties for both explicit and implicit graph representations.
Abstraction has been used in search and planning from the very beginning of AI. Many different methods and formalisms for abstraction have been proposed in the literature but they have been designed from various points of view and with varying purposes. Hence, these methods have been notoriously difficult to analyse and compare in a structured way. In order to improve upon this situation, we present a coherent and flexible framework for modelling abstraction (and abstraction-like) methods based on transformations on labelled graphs. Transformations can have certain method properties that are inherent in the abstraction methods and describe their fundamental modelling characteristics, and they can have certain instance properties that describe algorithmic and computational characteristics of problem instances. The usefulness of the framework is demonstrated by applying it to problems in both search and planning. First, we show that we can capture many search abstraction concepts (such as avoidance of backtracking between levels) and that we can put them into a broader context. We further model five different abstraction concepts from the planning literature. Analysing what method properties they have highlights their fundamental differences and similarities. Finally, we prove that method properties sometimes imply instance properties. Taking also those instance properties into account reveals important information about computational aspects of the five methods.
Compact representations of objects is a common concept in computer science. Automated planning can be viewed as a case of this concept: a planning instance is a compact implicit representation of a graph and the problem is to find a path (a plan) in this graph. While the graphs themselves are represented compactly as planning instances, the paths are usually represented explicitly as sequences of actions. Some cases are known where the plans always have compact representations, for example, using macros. We show that these results do not extend to the general case, by proving a number of bounds for compact representations of plans under various criteria, like efficient sequential or random access of actions. In addition to this, we show that our results have consequences for what can be gained from reformulating planning into some other problem. As a contrast to this we also prove a number of positive results, demonstrating restricted cases where plans do have useful compact representations, as well as proving that macro plans have favourable access properties. Our results are finally discussed in relation to other relevant contexts.
Complexity analysis of planning is problematic. Even very simple planning languages are PSPACE-complete, yet cannot model many simple problems naturally. Many languages with much more powerful features are also PSPACE-complete. It is thus difficult to separate planning languages in a useful way and to get complexity figures that better reflect reality.This paper introduces new methods for complexity analysis of planning and similar combinatorial search problems, in order to achieve more precision and complexity separations than standard methods allow. Padding instances with the solution size yields a complexity measure that is immune to this factor and reveals other causes of hardness, that are otherwise hidden. Further combining this method with limited nondeterminism improves the precision, making even finer separations possible. We demonstrate with examples how these methods can narrow the gap between theory and practice.
There are two major uses of abstraction in planning and search: refinement (where abstract solutions are extended into concrete solutions) and heuristics (where abstract solutions are used to compute heuristics for the original search space). These two approaches are usually viewed as unrelated in the literature. It is reasonable to believe, though, that they are related, since they are both intrinsically based on the structure of abstract search spaces. We take the first steps towards formally investigating their relationships, employing our recently introduced framework for analysing and comparing abstraction methods. By adding some mechanisms for expressing metric properties, we can capture concepts like admissibility and consistency of heuristics. We present an extensive study of how such metric properties relate to the properties in the original framework, revealing a number of connections between the refinement and heuristic approaches. This also provides new insights into, for example, Valtorta's theorem and spurious states.
Most planning formalisms allow instances with shortest plans of exponential length. While such instances are problematic, they are usually unavoidable and can occur in practice. There are several known cases of restricted planning problems where plans can be exponential but always have a compact (ie. polynomial) representation, often using recursive macros. Such compact representations are important since exponential plans are difficult both to use and to understand. We show that these results do not extend to the general case, by proving a number of bounds for compact representations of plans under various criteria, like efficient sequential or random access of actions. Further, we show that it is unlikely to get around this by reformulating planning into some other problem. The results are discussed in the context of abstraction, macros and plan explanation.
Complexity analysis based on the causal graphs of planning instances has emerged as a highly important area of research. In particular, tractability results have led to new methods for the identification of domain-independent heuristics. Important early examples of such tractability results have been presented by, for instance, Brafman & Domshlak and Katz & Keyder. More general results based on polytrees and bounding certain parameters were subsequently derived by Aghighi et al. and Ståhlberg. We continue this line of research by analyzing cost-optimal planning restricted to instances with a polytree causal graph, bounded domain size and bounded depth (i.e. the length of the longest directed path in the causal graph). We show that no further restrictions are necessary for tractability, thus generalizing the previous results. Our approach is based on a novel method of closely analysing optimal plans: we recursively decompose the causal graph in a way that allows for bounding the number of variable changes as a function of the depth, using a reording argument and a comparison with prefix trees of known size. We can then transform the planning instances into constraint satisfaction instances; an idea that has previously been exploited by, for example, Brafman & Domshlak and Bäckström. This allows us to utilise efficient algorithms for constraint optimisation over tree-structured instances.
The propositional planning problem is a notoriously difficult computational problem, which remains hard even under strong syntactical and structural restrictions. Given its difficulty it becomes natural to study planning in the context of parameterized complexity. In this paper we continue the work initiated by Downey, Fellows and Stege on the parameterized complexity of planning with respect to the parameter "length of the solution plan." We provide a complete classification of the parameterized complexity of the planning problem under two of the most prominent syntactical restrictions, i.e., the so called PUBS restrictions introduced by Backstrom and Nebel and restrictions on the number of preconditions and effects as introduced by Bylander. We also determine which of the considered fixed-parameter tractable problems admit a polynomial kernel and which do not. (C) 2015 Elsevier Inc. All rights reserved.
The propositional planning problem is a notoriously difficult computational problem. Downey et al. (1999) initiated the parameterized analysis of planning (with plan length as the parameter) and Bäckström et al. (2012) picked up this line of research and provided an extensive parameterized analysis under various restrictions, leaving open only one stubborn case. We continue this work and provide a full classification. In particular, we show that the case when actions have no preconditions and at most e postconditions is fixed-parameter tractable if e ≤ 2 and W[1]-complete otherwise. We show fixed-parameter tractability by a reduction to a variant of the Steiner Tree problem; this problem has been shown fixed-parameter tractable by Guo et al. (2007). If a problem is fixed-parameter tractable, then it admits a polynomial-time self-reduction to instances whose input size is bounded by a function of the parameter, called the kernel. For some problems, this function is even polynomial which has desirable computational implications. Recent research in parameterized complexity has focused on classifying fixed-parameter tractable problems on whether they admit polynomial kernels or not. We revisit all the previously obtained restrictions of planning that are fixed-parameter tractable and show that none of them admits a polynomial kernel unless the polynomial hierarchy collapses to its third level.
There has been a tremendous advance in domain-independent planning over the past decades, and planners have become increasingly efficient at finding plans. However, this has not been paired by any corresponding improvement in detecting unsolvable instances. Such instances are obviously important but largely neglected in planning. In other areas, such as constraint solving and model checking, much effort has been spent on devising methods for detecting unsolvability. We introduce a method for detecting unsolvable planning instances that is loosely based on consistency checking in constraint programming. Our method balances completeness against efficiency through a parameter k: the algorithm identifies more unsolvable instances but takes more time for increasing values of k. We present empirical data for our algorithm and some standard planners on a number of unsolvable instances, demonstrating that our method can be very efficient where the planners fail to detect unsolvability within reasonable resource bounds. We observe that planners based on the h^m heuristic or pattern databases are better than other planners for detecting unsolvability. This is not a coincidence since there are similarities (but also significant differences) between our algorithm and these two heuristic methods.
Many combinatorial search problems can be expressed as 'constraint satisfaction problems'. This class of problems is known to be NP-hard in general, but a number of restricted constraint classes have been identified which ensure tractability. This paper presents the first general results on combining tractable constraint classes to obtain larger, more general, tractable classes. We give examples to show that many known examples of tractable constraint classes, from a wide variety of different contexts, can be constructed from simpler tractable classes using a general method. We also construct several new tractable classes that have not previously been identified.
Expressive temporal reasoning formalisms are essential for AI. One family of such formalisms consists of disjunctive extensions of the simple temporal problem (STP). Such extensions are well studied in the literature and they have many important applications. It is known that deciding satisfiability of disjunctive STPs is NP-hard, while the fine-grained complexity of such problems is virtually unexplored. We present novel algorithms that exploit structural properties of the solution space and prove, assuming the Exponential-Time Hypothesis, that their worst-case time complexity is close to optimal. Among other things, we make progress towards resolving a long-open question concerning whether Allens interval algebra can be solved in single-exponential time, by giving a 2(O(n log log n)) algorithm for the special case of unit-length intervals.
We present four polynomial space and exponential time algorithms for variants of the EXACT SATISFIABILITY problem. First, an O(1.1120n) (where n is the number of variables) time algorithm for the NP-complete decision problem of EXACT 3-SATISFIABILITY, and then an O(1.1907n) time algorithm for the general decision problem of EXACT SATISFIABILITY. The best previous algorithms run in O(1.1193n) and O(1.2299n) time, respectively. For the #P-complete problem of counting the number of models for EXACT 3-SATISFIABILITY we present an O(1.1487n) time algorithm. We also present an O(1.2190n) time algorithm for the general problem of counting the number of models for EXACT SATISFIABILITY, presenting a simple reduction, we show how this algorithm can be used for computing the permanent of a 0/1 matrix. © 2004 Elsevier B.V. All rights reserved.
We present an O(1.3247^{n}) algorithm for counting the number of satisfying assignments for instances of 2-SAT and an O(1.6894^{n}) algorithm for instances of 3-SAT. This is an improvement compared to the previously best known algorithms running in O(1.381^{n}) and O(1.739^{n}) time, respectively.
We here present algorithms for counting models and max-weight models for 2SAT and 3SAT formulae. They use polynomial space and run in O(1.2561^{n}) and O(1.6737^{n}) time, respectively, where n is the number of variables. This is faster than the previously best algorithms for counting non-weighted models for 2SAT and 3SAT, which run in O(1.3247^{n}) and O(1.6894^{n}) time, respectively. In order to prove these time bounds, we develop new measures of formula complexity, allowing us to conveniently analyze the effects of certain factors with a large impact on the total running time. We also provide an algorithm for the restricted case of separable 2SAT formulae, with fast running times for well-studied input classes. For all three algorithms we present interesting applications, such as computing the permanent of sparse 0/1 matrices.
We introduce a binary parameter on optimisation problems called separation. The parameter is used to relate the approximation ratios of different optimisation problems; in other words, we can convert approximability (and non-approximability) result for one problem into (non)-approximability results for other problems. Our main application is the problem (weighted) maximum H-colourable subgraph (MAX H-COL), which is a restriction of the general maximum constraint satisfaction problem (MAX CSP) to a single, binary, and symmetric relation. Using known approximation ratios for MAX k-CUT, we obtain general asymptotic approximability results for MAX H-COL for an arbitrary graph H. For several classes of graphs, we provide near-optimal results under the unique games conjecture. We also investigate separation as a graph parameter. In this vein, we study its properties on circular complete graphs. Furthermore, we establish a close connection to work by Samal on cubical colourings of graphs. This connection shows that our parameter is closely related to a special type of chromatic number. We believe that this insight may turn out to be crucial for understanding the behaviour of the parameter, and in the longer term, for understanding the approximability of optimisation problems such as MAX H-COL.
The instances of the Weighted Maximum H-Colourable Subgraph problem (Max H-Col) are edge-weighted graphs G and the objective is to find a subgraph of G that has maximal total edge weight, under the condition that the subgraph has a homomorphism to H; note that for H=K_{k} this problem is equivalent to Max k-cut. Färnqvist et al. have introduced a parameter on the space of graphs that allows close study of the approximability properties of Max H-Col. Here, we investigate the properties of this parameter on circular complete graphs K_{p/q}, where 2p/q3. The results are extended to K_{4}-minor-free graphs. We also consider connections with Šámal's work on fractional covering by cuts: we address, and decide, two conjectures concerning cubical chromatic numbers.
For a fixed graph H, let RET(H) denote the problem of deciding whether a given input graph is retractable to H. We classify the complexity of RET(H) when H is a graph (with loops allowed) where each connected component has at most one cycle, i.e., a pseudoforest. In particular, this result extends the known complexity classifications of RET(H) for reflexive and irreflexive cycles to general cycles. Our approach is based mainly on algebraic techniques from universal algebra that previously have been used for analyzing the complexity of constraint satisfaction problems.
We study the complexity of structurally restricted homomorphism and constraint satisfaction problems. For every class of relational structures C , let LHom be the problem of deciding whether a structure A Î CA has a homomorphism to a given arbitrary structure B, when each element in A is only allowed a certain subset of elements of B as its image. We prove, under a certain complexity-theoretic assumption, that this list homomorphism problem is solvable in polynomial time if and only if all structures in C have bounded tree-width. The result is extended to the connected list homomorphism, edge list homomorphism, minimum cost homomorphism and maximum solution problems. We also show an inapproximability result for the minimum cost homomorphism problem.
A graph homomorphism is a vertex map which carries edges from a source graph to edges in a target graph. We Study the approximability properties of the Weigh feel Maximum H-Colourable Subgraph problem (MAX H-COL). The instances of this problem are edge-weighted graphs G and the objective is to find a subgraph of G that has maximal total edge weight, under the condition that the subgraph has a homomorphism to H note that for H = K-k this problem is equivalent to MAX k-CUT. To this end, we introduce a metric structure on the space of graphs which allows us to extend previously known approximability results to larger classes of graphs. Specifically, the approximation algorithms for MAX CUT by Goemans and Williamson and MAX k-CUT by Frieze and Jerrum can he used to yield non-trivial approximation results for MAX H-COL For a variety of graphs, we show near-optimality results under the Unique Games Conjecture. We also use our method for comparing the performance of Frieze andamp; Jerrums algorithm with Hastads approximation algorithm for general MAX 2-CSP. This comparison is, in most cases, favourable to Frieze andamp; Jerrum.
Classical propositional STRIPS planning is nothing but the search for a path in the state transition graph induced by the operators in the planning problem. What makes the problem hard is the size and the sometimes adverse structure of this graph. We conjecture that the search for a plan would be more efficient if there were only a small number of paths from the initial state to the goal state. To verify this conjecture, we define the notion of reduced operator sets and describe ways of finding such reduced sets. We demonstrate that some state-of-the-art planners run faster using reduced operator sets.
Planning with incomplete information may mean a number of different things, that certain facts of the initial state are not known, that operators can have random or nondeterministic effects, or that the plans created contain sensing operations and are branching. Study of the complexity of incomplete information planning has so far been concentrated on probabilistic domains, where a number of results have been found. We examine the complexity of planning in nondeterministic propositional domains. This differs from domains involving randomness, which has been well studied, in that for a nondeterministic choice, not even a probability distribution over the possible outcomes is known. The main result of this paper is that the non-branching plan existence problem in unobservable domains with an expressive operator formalism is EXPSPACE-complete. We also discuss several restrictions, which bring the complexity of the problem down to PSPACF-complete, and extensions to the fully and partially observable cases.
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.
Causal graphs are widely used in planning to capture the internal structure of planning instances. In the past, causal graphs have been exploited to generate hierarchical plans, to compute heuristics, and to identify classes of planning instances that are easy to solve. It is generally believed that planning is easier when the causal graph is acyclic. In this paper we show that this is not true in the worst case, proving that 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 pre-conditions. Having established that planning is hard for acyclic causal graphs, we study a subclass of planning instances with acyclic causal graphs whose variables have strongly connected domain transition graphs. For this class, we show that plan existence is easy, but that bounded plan existence is hard, implying that optimal planning is significantly harder than satisficing planning for this class.
Partly motivated by description logics, poor man's logics have been proposed as an interesting fragment of modal logics. A poor man's logic is a propositional modal logic where only literals and the connectives , , and are allowed. It is known that the complexity of the satisfiability problem may drop dramatically when going from a full modal logic to the corresponding poor man's logic, e.g., in the case of modal logic K one goes from PSPACEcomplete to coNP-complete. We prove that it is sometimes possible to extend poor man's logics with restricted disjunctions (i.e., clauses) without increasing the computational complexity. For Horn and Krom clauses, we provide necessary and sufficient conditions for when the resulting logic is polynomial-time. Such extensions correspond to allowing a restricted use of the union operator in description logics.
A boolean constraint satisfaction problem consists of some finite set of constraints (i.e., functions from 0/1-vectors to {0, 1}) and an instance of such a problem is a set of constraints applied to specified subsets of n boolean variables. The goal is to find an assignment to the variables which satisfy all constraint applications. The computational complexity of optimization problems in connection with such problems has been studied extensively but the results have relied on the assumption that the weights are non-negative. The goal of this article is to study variants of these optimization problems where arbitrary weights are allowed. For the four problems that we consider, we give necessary and sufficient conditions for when the problems can be solved in polynomial time. In addition, we show that the problems are NP-equivalent in all other cases. (C) 2000 Elsevier Science B.V. All rights reserved.
Computationally tractable planning problems reported in the literature have almost exclusively been defined by syntactical restrictions. To better exploit the inherent structure in problems, it is probably necessary to study also structural restrictions on the underlying state-transition graph. Such restrictions are typically hard to test since this graph is of exponential size. We propose an intermediate approach, using a state variable model for planning and defining restrictions on the state-transition graph for each state variable in isolation. We identify such restrictions which are tractable to test and we present a planning algorithm which is correct and runs in polynomial time under these restrictions.Moreover, we present an exhaustive map over the complexity results for planning under all combinations of four previously studied syntactical restrictions and our five new structural restrictions. This complexity map considers both the bounded and unbounded plan generation problem. Finally, we extend a provably correct, polynomial-time planner to plan for a miniature assembly line, which assembles toy cars. Although somewhat limited, this process has many similarities with real industrial processes.