Peter Jonsson

SODA Conference 2023 Conference Paper

Almost Consistent Systems of Linear Equations

• Konrad K. Dabrowski
• Peter Jonsson
• Sebastian Ordyniak
• George Osipov
• Magnus Wahlström

Checking whether a system of linear equations is consistent is a basic computational problem with ubiquitous applications. When dealing with inconsistent systems, one may seek an assignment that minimizes the number of unsatisfied equations. This problem is NP-hard and UGC-hard to approximate within any constant even for two-variable equations over the two-element field. We study this problem from the point of view of parameterized complexity, with the parameter being the number of unsatisfied equations. We consider equations defined over Euclidean domains—a family of commutative rings that generalize finite and infinite fields including the rationals, the ring of integers and many other structures. We show that if every equation contains at most two variables, the problem is fixed-parameter tractable. This generalizes many eminent graph separation problems such as Bipartization, Multiway Cut and Multicut parameterized by the size of the cutset. To complement this, we show that the problem is W[1]-hard when three or more variables are allowed in an equation, as well as for many commutative rings that are not Euclidean domains. On the technical side, we introduce the notion of important balanced subgraphs, generalizing important separators of Marx [Theor. Comput. Sci. 2006] to the setting of biased graphs. Furthermore, we use recent results on parameterized MinCSP [Kim et al. , SODA 2021] to efficiently solve a generalization of Multicut with disjunctive cut requests. * The full version of the paper can be accessed at https: //arxiv. org/abs/2208. 02732

ICAPS Conference 2023 Conference Paper

Planning over Integers: Compilations and Undecidability

• Daniel Gnad 0001
• Malte Helmert
• Peter Jonsson
• Alexander Shleyfman

Restricted Tasks (RT) are a special case of numeric planning characterized by numeric conditions that involve one numeric variable per formula and numeric effects that allow only the addition of constants. Despite this, RTs form an expressive class whose planning problem is undecidable. The restricted nature of RTs often makes problem modeling awkward and unnecessarily complicated. We show that this can be alleviated by compiling mathematical operations that are not natively supported into RTs using macro-like action sequences. With that, we can encode many features found in general numeric planning such as constant multiplication, addition of linear formulas, and integer division and residue. We demonstrate how our compilations can be used to capture challenging mathematical problems such as the (in)famous Collatz conjecture. Our approach additionally gives a simple undecidability proof for RTs, and the proof shows that the number of variables needed to construct an undecidable class of RTs is surprisingly low: two numeric and one propositional variable.

AIJ Journal 2023 Journal Article

Solving infinite-domain CSPs using the patchwork property

• Konrad K. Dabrowski
• Peter Jonsson
• Sebastian Ordyniak
• George Osipov

The constraint satisfaction problem (CSP) has important applications in computer science and AI. In particular, infinite-domain CSPs have been intensively used in subareas of AI such as spatio-temporal reasoning. Since constraint satisfaction is a computationally hard problem, much work has been devoted to identifying restricted problems that are efficiently solvable. One way of doing this is to restrict the interactions of variables and constraints, and a highly successful approach is to bound the treewidth of the underlying primal graph. Bodirsky & Dalmau (2013) [14] and Huang et al. (2013) [47] proved that CSP(Γ) can be solved in n f ( w ) time (where n is the size of the instance, w is the treewidth of the primal graph and f is a computable function) for certain classes of constraint languages Γ. We improve this bound to f ( w ) ⋅ n O ( 1 ), where the function f only depends on the language Γ, for CSPs whose basic relations have the patchwork property. Hence, such problems are fixed-parameter tractable and our algorithm is asymptotically faster than the previous ones. Additionally, our approach is not restricted to binary constraints, so it is applicable to a strictly larger class of problems than that of Huang et al. However, there exist natural problems that are covered by Bodirsky & Dalmau's algorithm but not by ours, and we begin investigating ways of generalising our results to larger families of languages. We also analyse our algorithm with respect to its running time and show that it is optimal (under the Exponential Time Hypothesis) for certain languages such as Allen's Interval Algebra.

AAAI Conference 2023 Conference Paper

Structurally Restricted Fragments of Numeric Planning – a Complexity Analysis

• Alexander Shleyfman
• Daniel Gnad
• Peter Jonsson

Numeric planning is known to be undecidable even under severe restrictions. Prior work has investigated the decidability boundaries by restricting the expressiveness of the planning formalism in terms of the numeric functions allowed in conditions and effects. We study a well-known restricted form of Hoffmann's simple numeric planning, which is undecidable. We analyze the complexity by imposing restrictions on the causal structure, exploiting a novel method for bounding variable domain sizes. First, we show that plan existence for tasks where all numeric variables are root nodes in the causal graph is in PSPACE. Second, we show that for tasks with only numeric leaf variables the problem is decidable, and that it is in PSPACE if the propositional state space has a fixed size. Our work lays a strong foundation for future investigations of structurally more complex tasks. From a practical perspective, our method allows to employ heuristics and methods that are geared towards finite variable domains (such as pattern database heuristics or decoupled search) to solve non-trivial families of numeric planning problems.

AIJ Journal 2022 Journal Article

A framework for analysing state-abstraction methods

• Christer Bäckström
• Peter Jonsson

Abstraction has been used in combinatorial search and action planning from the very beginning of AI. Many different methods and formalisms for state 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 graph transformations. The usefulness of the framework is demonstrated by applying it to problems in both search and planning. We model six different abstraction methods from the planning literature and analyse their intrinsic properties. We show how to capture many search abstraction concepts (such as avoiding backtracking between levels) and how to put them into a broader context. We also use the framework to identify and investigate connections between refinement and heuristics—two concepts that have usually been considered as unrelated in the literature. This provides new insights into various topics, e. g. Valtorta's theorem and spurious states. We finally extend the framework with composition of transformations to accommodate for abstraction hierarchies, and other multi-level concepts. We demonstrate the latter by modelling and analysing the merge-and-shrink abstraction method.

JAIR Journal 2022 Journal Article

Computational Short Cuts in Infinite Domain Constraint Satisfaction

• Peter Jonsson
• Victor Lagerkvist
• Sebastian Ordyniak

A backdoor in a finite-domain CSP instance is a set of variables where each possible instantiation moves the instance into a polynomial-time solvable class. Backdoors have found many applications in artificial intelligence and elsewhere, and the algorithmic problem of finding such backdoors has consequently been intensively studied. Sioutis and Janhunen have proposed a generalised backdoor concept suitable for infinite-domain CSP instances over binary constraints. We generalise their concept into a large class of CSPs that allow for higher-arity constraints. We show that this kind of infinite-domain backdoors have many of the positive computational properties that finite-domain backdoors have: the associated computational problems are fixed parameter tractable whenever the underlying constraint language is finite. On the other hand, we show that infinite languages make the problems considerably harder: the general backdoor detection problem is W[2]-hard and fixed-parameter tractability is ruled out under standard complexity-theoretic assumptions. We demonstrate that backdoors may have suboptimal behaviour on binary constraints—this is detrimental from an AI perspective where binary constraints are predominant in, for instance, spatiotemporal applications. In response to this, we introduce sidedoors as an alternative to backdoors. The fundamental computational problems for sidedoors remain fixed-parameter tractable for finite constraint language (possibly also containing non-binary relations). Moreover, the sidedoor approach has appealing computational properties that sometimes leads to faster algorithms than the backdoor approach.

AAAI Conference 2022 Conference Paper

Resolving Inconsistencies in Simple Temporal Problems: A Parameterized Approach

• Konrad K. Dabrowski
• Peter Jonsson
• Sebastian Ordyniak
• George Osipov

The simple temporal problem (STP) is one of the most influential reasoning formalisms for representing temporal information in AI. We study the problem of resolving inconsistency of data encoded in the STP. We prove that the problem of identifying a maximally large consistent subset of data is NP-hard. In practical instances, it is reasonable to assume that the amount of erroneous data is small. We therefore parameterize by the number of constraints that need to be removed to achieve consistency. Using tools from parameterized complexity we design fixed-parameter tractable algorithms for two large fragments of the STP. Our main algorithmic results employ reductions to the Directed Subset Feedback Arc Set problem and iterative compression combined with an efficient algorithm for the Edge Multicut problem. We complement our algorithmic results with hardness results that rule out fixed-parameter tractable algorithms for all remaining non-trivial fragments of the STP (under standard complexity-theoretic assumptions). Together, our results give a full classification of the classical and parameterized complexity of the problem.

AIJ Journal 2021 Journal Article

Acyclic orders, partition schemes and CSPs: Unified hardness proofs and improved algorithms

• Peter Jonsson
• Victor Lagerkvist
• George Osipov

Many computational problems arising in, for instance, artificial intelligence can be realized as infinite-domain constraint satisfaction problems (CSPs) based on partition schemes: a set of pairwise disjoint binary relations (containing the equality relation) whose union spans the underlying domain and which is closed under converse. We first consider partition schemes that contain an acyclic order and where the constraint language contains all unions of the basic relations; such CSPs are frequently occurring in e. g. temporal and spatial reasoning. We identify properties of such orders which, when combined, are sufficient to establish NP-hardness of the CSP and strong lower bounds under the exponential-time hypothesis, even for degree-bounded problems. This result explains, in a uniform way, many existing hardness results from the literature, and shows that it is impossible to obtain subexponential time algorithms unless the exponential-time hypothesis fails. However, some of these problems (including several important temporal problems), despite likely not being solvable in subexponential time, admit non-trivial improved exponential-time algorithm, and we present a novel improved algorithm for RCC-8 and related formalisms.

JAIR Journal 2021 Journal Article

Computational Complexity of Computing Symmetries in Finite-Domain Planning

• Alexander Shleyfman
• Peter Jonsson

Symmetry-based pruning is a powerful method for reducing the search effort in finitedomain planning. This method is based on exploiting an automorphism group connected to the ground description of the planning task { these automorphisms are known as structural symmetries. In particular, we are interested in the StructSym problem where the generators of this group are to be computed. It has been observed in practice that the StructSym problem is surprisingly easy to solve. We explain this phenomenon by showing that StructSym is GI-complete, i.e., the graph isomorphism problem is polynomial-time equivalent to it and, consequently, solvable in quasi-polynomial time. This implies that it is solvable substantially faster than most computationally hard problems encountered in AI. We accompany this result by identifying natural restrictions of the planning task and its causal graph that ensure that StructSym can be solved in polynomial time. Given that the StructSym problem is GI-complete and thus solvable quite efficiently, it is interesting to analyse if other symmetries (than those that are encompassed by the StructSym problem) can be computed and/or analysed efficiently, too. To this end, we present a highly negative result: checking whether there exists an automorphism of the state transition graph that maps one state s into another state t is a PSPACE-hard problem and, consequently, at least as hard as the planning problem itself.

JAIR Journal 2021 Journal Article

Cost-optimal Planning, Delete Relaxation, Approximability, and Heuristics

• Christer Bäckström
• Peter Jonsson
• Sebastian Ordyniak

Cost-optimal planning is a very well-studied topic within planning, and it has proven to be computationally hard both in theory and in practice. Since cost-optimal planning is an optimisation problem, it is natural to analyse it through the lens of approximation. An important reason for studying cost-optimal planning is heuristic search; heuristic functions that guide the search in planning can often be viewed as algorithms solving or approximating certain optimisation problems. Many heuristic functions (such as the ubiquitious h+ heuristic) are based on delete relaxation, which ignores negative effects of actions. Planning for instances where the actions have no negative effects is often referred to as monotone planning. The aim of this article is to analyse the approximability of cost-optimal monotone planning, and thus the performance of relevant heuristic functions. Our findings imply that it may be beneficial to study these kind of problems within the framework of parameterised complexity and we initiate work in this direction.

AAAI Conference 2021 Conference Paper

Disjunctive Temporal Problems under Structural Restrictions

• Konrad K Dabrowski
• Peter Jonsson
• Sebastian Ordyniak
• George Osipov

The disjunctive temporal problem (DTP) is an expressive temporal formalism that extends Dechter et al. ’s simple temporal problem. The DTP is well studied in the literature and has many important applications. It is known that deciding satisfiability of DTPs is NP-hard and that, in many cases, single-exponential algorithms (running in O(cn ) time) do not exist under the Exponential-Time Hypothesis. The computational hardness makes it worthwhile to identify restricted problems that are efficiently solvable. One way of doing this is to restrict the interactions of variables and constraints. We show that instances of DTP of any arity with integers bounded by poly(n) can be solved in nf(w) time, where n denotes the problem size, w is the treewidth of the incidence graph and f is a computable function; in other words, this problem is in the complexity class XP and it can be solved in polynomial time whenever w is fixed. We complement this result by showing that binary DTPs that only involve the integers 0 and 1 are not fixed-parameter tractable with respect to treewidth, i. e. they do not admit a f(w) · poly(n) time algorithm for any computable function f, under standard complexity assumptions. For instances with unbounded integers, we show that even binary DTPs parameterized by treewidth cannot be in XP, unless P = NP.

AAAI Conference 2021 Conference Paper

Solving Infinite-Domain CSPs Using the Patchwork Property

• Konrad K Dabrowski
• Peter Jonsson
• Sebastian Ordyniak
• George Osipov

The constraint satisfaction problem (CSP) has important applications in computer science and AI. In particular, infinitedomain CSPs have been intensively used in subareas of AI such as spatio-temporal reasoning. Since constraint satisfaction is a computationally hard problem, much work has been devoted to identifying restricted problems that are efficiently solvable. One way of doing this is to restrict the interactions of variables and constraints, and a highly successful approach is to bound the treewidth of the underlying primal graph. Bodirsky & Dalmau [J. Comput. System. Sci. 79(1), 2013] and Huang et al. [Artif. Intell. 195, 2013] proved that CSP(Γ) can be solved in nf(w) time (where n is the size of the instance, w is the treewidth of the primal graph and f is a computable function) for certain classes of constraint languages Γ. We improve this bound to f(w) · nO(1), where the function f only depends on the language Γ, for CSPs whose basic relations have the patchwork property. Hence, such problems are fixed-parameter tractable and our algorithm is asymptotically faster than the previous ones. Additionally, our approach is not restricted to binary constraints, so it is applicable to a strictly larger class of problems than that of Huang et al. However, there exist natural problems that are covered by Bodirsky & Dalmau’s algorithm but not by ours.

TCS Journal 2021 Journal Article

The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems

• Peter Jonsson
• Victor Lagerkvist
• Johannes Schmidt
• Hannes Uppman

Obtaining lower bounds for NP-hard problems has for a long time been an active area of research. Algebraic techniques introduced by Jonsson et al. (2017) [4] show that the fine-grained time complexity of the parameterized Image 1 problem correlates to the lattice of strong partial clones. With this ordering they isolated a relation R such that Image 2 can be solved at least as fast as any other NP-hard Image 1 problem. In this paper we extend this method and show that such languages also exist for the surjective SAT problem, the max ones problem, the propositional abduction problem, and the Boolean valued constraint satisfaction problem over finite-valued constraint languages. These languages may be interesting when investigating the borderline between polynomial time, subexponential time and exponential-time algorithms since they in a precise sense can be regarded as NP-hard problems with minimum time complexity. Indeed, with the help of these languages we relate all of the above problems to the exponential time hypothesis (ETH) in several different ways.

KR Conference 2020 Conference Paper

Fine-Grained Complexity of Temporal Problems

• Konrad K. Dabrowski
• Peter Jonsson
• Sebastian Ordyniak
• George Osipov

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 Allen's interval algebra can be solved in single-exponential time, by giving a 2^{O(nloglog(n))} algorithm for the special case of unit-length intervals.

IJCAI Conference 2020 Conference Paper

Lower Bounds and Faster Algorithms for Equality Constraints

• Peter Jonsson
• Victor Lagerkvist

We study the fine-grained complexity of NP-complete, infinite-domain constraint satisfaction problems (CSPs) parameterised by a set of first-order definable relations (with equality). Such CSPs are of central importance since they form a subclass of any infinite-domain CSP parameterised by a set of first-order definable relations. We prove that under the randomised exponential-time hypothesis it is not possible to find c > 1 such that a CSP over an arbitrary finite equality language is solvable in O(c^n) time (n is the number of variables). Stronger lower bounds are possible for infinite equality languages where we rule out the existence of 2^o(n log n) time algorithms; a lower bound which also extends to satisfiability modulo theories solving for an arbitrary background theory. Despite these lower bounds we prove that for each c > 1 there exists an NP-hard equality CSP solvable in O(c^n) time. Lower bounds like these immediately ask for closely matching upper bounds, and we prove that a CSP over a finite equality language is always solvable in O(c^n) time for a fixed c.

IJCAI Conference 2019 Conference Paper

A Refined Understanding of Cost-optimal Planning with Polytree Causal Graphs

• Christer Bäckström
• Peter Jonsson
• Sebastian Ordyniak

Complexity analysis based on the causal graphs of planning instances is a highly important research area. In particular, tractability results have led to new methods for constructing domain-independent heuristics. Important early examples of such results were 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 for instances with a polytree causal graph, bounded domain size and bounded depth. 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 then transform the planning instances into tree-structured constraint satisfaction instances.

SoCS Conference 2018 Conference Paper

A Refined Understanding of Cost-Optimal Planning with Polytree Causal Graphs

• Christer Bäckström
• Peter Jonsson
• Sebastian Ordyniak

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.

IJCAI Conference 2018 Conference Paper

Classification Transfer for Qualitative Reasoning Problems

• Manuel Bodirsky
• Peter Jonsson
• Barnaby Martin
• Antoine Mottet

We study formalisms for temporal and spatial reasoning in the modern context of Constraint Satisfaction Problems (CSPs). We show how questions on the complexity of their subclasses can be solved using existing results via the powerful use of primitive positive (pp) interpretations and pp-homotopy. We demonstrate the methodology by giving a full complexity classification of all constraint languages that are first-order definable in Allen's Interval Algebra and contain the basic relations (s) and (f). In the case of the Rectangle Algebra we answer in the affirmative the old open question as to whether ORD-Horn is a maximally tractable subset among the (disjunctive, binary) relations. We then generalise our results for the Rectangle Algebra to the r-dimensional Block Algebra.

AIJ Journal 2018 Journal Article

Constants and finite unary relations in qualitative constraint reasoning

• Peter Jonsson

Extending qualitative CSPs with the ability of restricting selected variables to finite sets of possible values has been proposed as an interesting research direction with important applications, cf. “Qualitative constraint satisfaction problems: an extended framework with landmarks” by Li, Liu, and Wang (2013) [48]. Previously presented complexity results for this kind of extended formalisms have typically focused on concrete examples and not on general principles. We propose three general methods. The first two methods are based on analysing the given CSP from a model-theoretical perspective, while the third method is based on directly analysing the growth of the representation of solutions. We exemplify the methods on temporal and spatial formalisms including Allen's algebra and RCC-5.

IJCAI Conference 2018 Conference Paper

Novel Structural Parameters for Acyclic Planning Using Tree Embeddings

• Christer Bäckström
• Peter Jonsson
• Sebastian Ordyniak

We introduce two novel structural parameters for acyclic planning (planning restricted to instances with acyclic causal graphs): up-depth and down-depth. We show that cost-optimal acyclic planning restricted to instances with bounded domain size and bounded up- or down-depth can be solved in polynomial time. For example, many of the tractable subclasses based on polytrees are covered by our result. We analyze the parameterized complexity of planning with bounded up- and down-depth: in a certain sense, down-depth has better computational properties than up-depth. Finally, we show that computing up- and down-depth are fixed-parameter tractable problems, just as many other structural parameters that are used in computer science. We view our results as a natural step towards understanding the complexity of acyclic planning with bounded treewidth and other parameters.

TCS Journal 2018 Journal Article

Tractability conditions for numeric CSPs

• Peter Jonsson
• Johan Thapper

The computational complexity of the constraint satisfaction problem (CSP) with semilinear relations over the reals has gained recent attraction. As a result, its complexity is known for all finite sets of semilinear relations containing the relation R + = { ( x, y, z ) ∈ R 3 | x + y = z }. We consider larger and more expressive classes of relations such as semialgebraic and o-minimal relations. We present a general result for characterising computationally hard fragments and, under certain side conditions, this result implies that polynomial-time solvable fragments are only to be found within two limited families of sets of relations. In the setting of semialgebraic relation, our result takes on a simplified form and we provide a full complexity classification for constraint languages that consist of algebraic varieties. Full classifications like the one obtained here for algebraic varieties or the one for semilinear relations appear to be rare and we discuss several barriers for obtaining further such results. These barriers have strong connections with well-known open problems concerning the complexity of various restrictions of convex programming.

MFCS Conference 2018 Conference Paper

Why are CSPs Based on Partition Schemes Computationally Hard?

• Peter Jonsson
• Victor Lagerkvist

Many computational problems arising in, for instance, artificial intelligence can be realized as infinite-domain constraint satisfaction problems (CSPs) based on partition schemes: a set of pairwise disjoint binary relations (containing the equality relation) whose union spans the underlying domain and which is closed under converse. We first consider partition schemes that contain a strict partial order and where the constraint language contains all unions of the basic relations; such CSPs are frequently occurring in e. g. temporal and spatial reasoning. We identify three properties of such orders which, when combined, are sufficient to establish NP-hardness of the CSP. This result explains, in a uniform way, many existing hardness results from the literature. More importantly, this result enables us to prove that CSPs of this kind are not solvable in subexponential time unless the exponential-time hypothesis (ETH) fails. We continue by studying constraint languages based on partition schemes but where relations are built using disjunctions instead of unions; such CSPs appear naturally when analysing first-order definable constraint languages. We prove that such CSPs are NP-hard even in very restricted settings and that they are not solvable in subexponential time under the randomised ETH. In certain cases, we can additionally show that they cannot be solved in O(c^n) time for any c >= 0.

JAIR Journal 2017 Journal Article

A Model-Theoretic View on Qualitative Constraint Reasoning

• Manuel Bodirsky
• Peter Jonsson

Qualitative reasoning formalisms are an active research topic in artificial intelligence. In this survey we present a model-theoretic perspective on qualitative constraint reasoning and explain some of the basic concepts and results in an accessible way. In particular, we discuss the significance of omega-categoricity for qualitative reasoning, of primitive positive interpretations for complexity analysis, and of Datalog as a unifying language for describing local consistency algorithms.

AIJ Journal 2017 Journal Article

An initial study of time complexity in infinite-domain constraint satisfaction

• Peter Jonsson
• Victor Lagerkvist

The constraint satisfaction problem (CSP) is a widely studied problem with numerous applications in computer science and artificial intelligence. For infinite-domain CSPs, there are many results separating tractable and NP-hard cases while upper and lower bounds on the time complexity of hard cases are virtually unexplored. Hence, we initiate a study of the worst-case time complexity of such CSPs. We analyze backtracking algorithms and determine upper bounds on their time complexity. We present asymptotically faster algorithms based on enumeration techniques and we show that these algorithms are applicable to well-studied problems in, for instance, temporal reasoning. Finally, we prove non-trivial lower bounds applicable to many interesting CSPs, under the assumption that certain complexity-theoretic assumptions hold. The gap between upper and lower bounds is in many cases surprisingly small, which suggests that our upper bounds cannot be significantly improved.

TCS Journal 2017 Journal Article

Circuit satisfiability and constraint satisfaction around Skolem Arithmetic

• Christian Glaßer
• Peter Jonsson
• Barnaby Martin

We study interactions between Skolem Arithmetic and certain classes of Circuit Satisfiability and Constraint Satisfaction Problems (CSPs). We revisit results of Glaßer et al. [1] in the context of CSPs and settle the major open question from that paper, finding a certain satisfiability problem on circuits—involving complement, intersection, union and multiplication—to be decidable. This we prove using the decidability of Skolem Arithmetic. Then we solve a second question left open in [1] by proving a tight upper bound for the similar circuit satisfiability problem involving just intersection, union and multiplication. We continue by studying first-order expansions of Skolem Arithmetic without constants, ( N; × ), as CSPs. We find already here a rich landscape of problems with non-trivial instances that are in P as well as those that are NP-complete.

JAIR Journal 2017 Journal Article

Time and Space Bounds for Planning

• Christer Bäckström
• Peter Jonsson

There is an extensive literature on the complexity of planning, but explicit bounds on time and space complexity are very rare. On the other hand, problems like the constraint satisfaction problem (CSP) have been thoroughly analysed in this respect. We provide a number of upper- and lower-bound results (the latter based on various complexity-theoretic assumptions such as the Exponential Time Hypothesis) for both satisficing and optimal planning. We show that many classes of planning instances exhibit a dichotomy: either they can be solved in polynomial time or they cannot be solved in subexponential time. In many cases, we can even prove closely matching upper and lower bounds. Our results also indicate, analogously to CSPs, the existence of sharp phase transitions. We finally study and discuss the trade-off between time and space. In particular, we show that depth-first search may sometimes be a viable option for planning under severe space constraints.

MFCS Conference 2017 Conference Paper

Time Complexity of Constraint Satisfaction via Universal Algebra

• Peter Jonsson
• Victor Lagerkvist
• Biman Roy

The exponential-time hypothesis (ETH) states that 3-SAT is not solvable in subexponential time, i. e. not solvable in O(c^n) time for arbitrary c > 1, where n denotes the number of variables. Problems like k-SAT can be viewed as special cases of the constraint satisfaction problem (CSP), which is the problem of determining whether a set of constraints is satisfiable. In this paper we study the worst-case time complexity of NP-complete CSPs. Our main interest is in the CSP problem parameterized by a constraint language Gamma (CSP(Gamma)), and how the choice of Gamma affects the time complexity. It is believed that CSP(Gamma) is either tractable or NP-complete, and the algebraic CSP dichotomy conjecture gives a sharp delineation of these two classes based on algebraic properties of constraint languages. Under this conjecture and the ETH, we first rule out the existence of subexponential algorithms for finite domain NP-complete CSP(Gamma) problems. This result also extends to certain infinite-domain CSPs and structurally restricted CSP(Gamma) problems. We then begin a study of the complexity of NP-complete CSPs where one is allowed to arbitrarily restrict the values of individual variables, which is a very well-studied subclass of CSPs. For such CSPs with finite domain D, we identify a relation SD such that (1) CSP({SD}) is NP-complete and (2) if CSP(Gamma) over D is NP-complete and solvable in O(c^n) time, then CSP({SD}) is solvable in O(c^n) time, too. Hence, the time complexity of CSP({SD}) is a lower bound for all CSPs of this particular kind. We also prove that the complexity of CSP({SD}) is decreasing when |D| increases, unless the ETH is false. This implies, for instance, that for every c>1 there exists a finite-domain Gamma such that CSP(Gamma) is NP complete and solvable in O(c^n) time.

ECAI Conference 2016 Conference Paper

Analysing Approximability and Heuristics in Planning Using the Exponential-Time Hypothesis

• Meysam Aghighi
• Christer Bäckström
• Peter Jonsson
• Simon Ståhlberg

Cost-optimal planning has become a very well-studied topic within planning. Needless to say, cost-optimal planning has proven to be computationally hard both theoretically and in practice. Since cost-optimal planning is an optimisation problem, it is natural to analyse it from an approximation point of view. Even though such studies may be valuable in themselves, additional motivation is provided by the fact that there is a very close link between approximability and the performance of heuristics used in heuristic search. The aim of this paper is to analyse approximability (and indirectly the performance of heuristics) with respect to lower time bounds. That is, we are not content by merely classifying problems into complexity classes - we also study their time complexity. This is achieved by replacing standard complexity-theoretic assumptions (such as P ≠ NP) with the exponential time hypothesis (ETH). This enables us to analyse, for instance, the performance of the h+heuristic and obtain general trade-off results that correlate approximability bounds with bounds on time complexity.

ECAI Conference 2016 Conference Paper

Finite Unary Relations and Qualitative Constraint Satisfaction

• Peter Jonsson

Extending qualitative CSPs with the ability of restricting selected variables to finite sets of possible values has been proposed as an important research direction with important applications. Complexity results for this kind of formalisms have appeared in the literature but they focus on concrete examples and not on general principles. We propose three general methods. The first two methods are based on analysing the given CSP from a model-theoretical perspective, while the third method is based on directly analysing the growth of the representation of solutions. We exemplify our methods on temporal and spatial formalisms including Allen's algebra and RCC5.

ECAI Conference 2016 Conference Paper

Upper and Lower Time and Space Bounds for Planning

• Christer Bäckström
• Peter Jonsson

There is an extensive literature on the complexity of planning, but explicit bounds on time and space complexity are very rare. On the other hand, problems like the constraint satisfaction problem have been thoroughly analysed in this respect. We provide a number of upper and lower bound results for both plan satisfiability (PSAT) and length-optimal planning (LOP), with an emphasis on monotone planning (where actions have only positive effects) which is used in, for instance, h+and similar heuristics. Let v and a be the number of variables and actions, respectively. We consider both restrictions on the number and polarity of preconditions and effects of actions and the PUBS restrictions in SAS+. For all such classes, we show that PSAT and LOP is either tractable or cannot be solved in subexponential time 2o( v) or time 2o( a) , unless the so-called Exponential Time Hypothesis (ETH) is false. There is also a sharp transition: monotone LOP can be solved in time 2o( v) ifbut not if a∈ Ω ( v) . We also study upper bounds and discuss the trade-off between time and space, providing a polynomial-space algorithm for monotone LOP that beats depth-first search in most cases. This raises the important question how lower bounds are affected by polynomial space restrictions.

TCS Journal 2015 Journal Article

Constructing NP-intermediate problems by blowing holes with parameters of various properties

• Peter Jonsson
• Victor Lagerkvist
• Gustav Nordh

The search for natural NP-intermediate problems is one of the holy grails within computational complexity. Ladner's original diagonalization technique for generating NP-intermediate problems, blowing holes, has a serious shortcoming: it creates problems with a highly artificial structure by arbitrarily removing certain problem instances. In this article we limit this problem by generalizing Ladner's method to use parameters with various characteristics. This allows one to define more fine-grained parameters, resulting in NP-intermediate problems where we only blow holes in a controlled subset of the problem. We begin by fully characterizing the problems that admit NP-intermediate subproblems for a broad and natural class of parameterizations, and extend the result further such that structural CSP restrictions based on parameters that are hard to compute (such as tree-width) are covered, thereby generalizing a result by Grohe. For studying certain classes of problems, including CSPs parameterized by constraint languages, we consider more powerful parameterizations. First, we identify a new method for obtaining constraint languages Γ such that CSP ( Γ ) are NP-intermediate. The sets Γ can have very different properties compared to previous constructions (by, for instance, Bodirsky & Grohe) and provides insights into the algebraic approach for studying the complexity of infinite-domain CSPs. Second, we prove that the propositional abduction problem parameterized by constraint languages admits NP-intermediate problems. This settles an open question posed by Nordh & Zanuttini.

AAAI Conference 2015 Conference Paper

Tractable Cost-Optimal Planning over Restricted Polytree Causal Graphs

• Meysam Aghighi
• Peter Jonsson
• Simon Ståhlberg

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.

AIJ Journal 2014 Journal Article

Limitations of acyclic causal graphs for planning

• Anders Jonsson
• Peter Jonsson
• Tomas Lööw

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.

AAAI Conference 2014 Conference Paper

Oversubscription Planning: Complexity and Compilability

• Meysam Aghighi
• Peter Jonsson

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 & Geffner.

IJCAI Conference 2013 Conference Paper

Bridging the Gap Between Refinement and Heuristics in Abstraction

• Christer Bäckström
• Peter Jonsson

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.

SODA Conference 2013 Conference Paper

Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis

• Peter Jonsson
• Victor Lagerkvist
• Gustav Nordh
• Bruno Zanuttini

The construction of exact exponential-time algorithms for NP-complete problems has for some time been a very active research area. Unfortunately, there is a lack of general methods for studying and comparing the time complexity of algorithms for such problems. We propose such a method based on clone theory and demonstrate it on the SAT problem. Schaefer has completely classified the complexity of SAT with respect to the set of allowed relations and proved that this parameterized problem exhibits a dichotomy: it is either in P or is NP-complete. We show that there is a certain partial order on the NP-complete SAT problems with a close connection to their worst-case time complexities; if a problem SAT( S ) is below a problem SAT( S′ ) in this partial order, then SAT( S′ ) cannot be solved strictly faster than SAT( S ). By using this order, we identify a relation R such that SAT({ R }) is the computationally easiest NP-complete SAT( S ) problem. This result may be interesting when investigating the borderline between P and NP since one appealing way of studying this borderline is to identify problems that, in some sense, are situated close to it (such as a ‘very hard’ problem in P or a ‘very easy’ NP-complete problem). We strengthen the result by showing that SAT({ R })-2 (i. e. SAT({ R }) restricted to instances where no variable appears more than twice) is NP-complete, too. This is in contrast to, for example, l-in-3-SAT (or even CNF-SAT), which is in P under the same restriction. We then relate SAT({ R })-2 to the exponential-time hypothesis (ETH) and show that ETH holds if and only if SAT({ R })-2 is not sub-exponential. This constitutes a strong connection between ETH and the SAT problem under both severe relational and severe structural restrictions, and it may thus serve as a tool for studying the borderline between sub-exponential and exponential problems. In the process, we also prove a stronger version of Impagliazzo et al. 's sparsification lemma for k -SAT; namely that all finite Boolean constraint languages S and S′ such that SAT(·) is NP-complete can be sparsified into each other. This should be compared with Santhanam and Srinivasan's recent negative result which states that the same does not hold for all infinite Boolean constraint languages.

AIJ Journal 2013 Journal Article

Computational complexity of linear constraints over the integers

• Peter Jonsson
• Tomas Lööw

Temporal reasoning problems arise in many areas of AI, including planning, natural language understanding, and reasoning about physical systems. The computational complexity of continuous-time temporal constraint reasoning is fairly well understood. There are, however, many different cases where discrete time must be considered; various scheduling problems and reasoning about sampled physical systems are two examples. Here, the complexity of temporal reasoning is not as well-studied nor as well-understood. In order to get a better understanding, we consider the powerful Horn disjunctive linear relations (Horn DLR) formalism adapted for discrete time and study its computational complexity. We show that the full formalism is NP-hard and identify several maximal tractable subclasses. We also ‘lift’ the maximality results to obtain hardness results for other families of constraints. Finally, we discuss how the results and techniques presented in this paper can be used for studying even more expressive classes of temporal constraints.

SoCS Conference 2013 Conference Paper

Fast Detection of Unsolvable Planning Instances Using Local Consistency

• Christer Bäckström
• Peter Jonsson
• Simon Ståhlberg

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.

ICAPS Conference 2013 Conference Paper

When Acyclicity Is Not Enough: Limitations of the Causal Graph

• Anders Jonsson 0001
• Peter Jonsson
• Tomas Lööw

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.

SoCS Conference 2012 Conference Paper

Abstracting Abstraction in Search II: Complexity Analysis

• Christer Bäckström
• Peter Jonsson

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.

KR Conference 2012 Conference Paper

Abstracting Abstraction in Search with Applications to Planning

• Christer Bäckström
• Peter Jonsson

we restrict ourselves in this way; its use dates back to A B STRIPS (Sacerdoti 1974) and even to the first version of GPS (Newell, Shaw, and Simon 1959). In order for abstraction to be useful, the abstract instance should be easier to solve and the total time spent should be less than without using abstraction. This is a reasonable requirement, yet it has turned out very difficult to achieve in practice. It has been demonstrated in many ways that abstraction can be very effective at decreasing overall solution time but few, if any, methods give any guarantees. For instance, Knoblock (1994) proposed a way to automatically create abstractions and demonstrated that it could give exponential speed-up in certain cases while Bäckström and Jonsson (1995) showed that the method can also backfire by creating solutions that are exponentially longer than the optimal solutions. Abstraction is thus a method that can strike both ways and it requires a careful analysis of the application domain to know if abstraction is useful or not. 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. 1 1. 1 A large number of different abstraction and abstractionlike methods appear in the literature. Unfortunately, many of these methods are tied to particular formalisms which make them difficult to analyse and compare in a meaningful way. We present a framework for comparing and analysing abstraction and abstraction-like methods based on transformations between labelled graphs. The idea of using functions (typically homomorphisms) on graphs (or other structures) for describing abstractions is very natural and has appeared in the literature earlier, cf. Holte et al. (1996) or Helmert, Haslum, and Hoffmann (2007). We extend this idea by viewing transformations as tuples hf, Ri where, loosely speaking, the function f describes the “structure” of the abstracted graph and R gives an “interpretation” of the abstracted labels. This gives us a plethora of possibilities to model and study different kinds of abstraction-like methods. We stress that we do not set out to create a grand theory of abstraction. There are attempts in the literature to define and study abstraction on a very general level which allow for an in-depth treatment of ontological aspects, cf. Giunchiglia and Walsh (1992) or Pandurang Nayak and Levy (1995). Our approach is much more pragmatic, and it is first and foremost intended for studying computational aspects of abstraction in search. This does not exclude that it may be useful in other contexts but we view this as an added bonus and not a primary goal. We also want to point out that our pur-

ECAI Conference 2012 Conference Paper

From Macro Plans to Automata Plans

• Christer Bäckström
• Anders Jonsson 0001
• Peter Jonsson

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.

ECAI Conference 2012 Conference Paper

Macros, Reactive Plans and Compact Representations

• Christer Bäckström
• Anders Jonsson 0001
• Peter Jonsson

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.

AAAI Conference 2012 Conference Paper

The Complexity of Planning Revisited — A Parameterized Analysis

• Christer Bäckström
• Yue Chen
• Peter Jonsson
• Sebastian Ordyniak
• Stefan Szeider

The early classifications of the computational complexity of planning under various restrictions in STRIPS (Bylander) and SAS+ (Bäckström 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 have seemed 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.

SoCS Conference 2011 Conference Paper

All PSPACE-Complete Planning Problems Are Equal but Some Are More Equal than Others

• Christer Bäckström
• Peter Jonsson

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 non-determinism improves the precision, making even finer separations possible. We demonstrate with examples how these methods can narrow the gap between theory and practice.

IJCAI Conference 2011 Conference Paper

Discrete-Time Temporal Reasoning with Horn DLRs

• Peter Jonsson
• Tomas L
• ouml;
• ouml; w

Temporal reasoning problems arise in many areas of AI, including planning, natural language understanding, and reasoning about physical systems. The computational complexity of continuous-time temporal constraint reasoning is fairly well understood. There are, however, many different cases where discrete time must be considered; various scheduling problems and reasoning about sampled physical systems are two examples. Here, the complexity of temporal reasoning is not as well-studied nor as well-understood. In order to get a better understanding, we consider the powerful Horn DLR formalism adapted for discrete time and study its computational complexity. We show that the full formalism is NP-hard and identify several maximal tractable subclasses. We also 'lift' the maximality results to obtain hardness results for other families of constraints. Finally, we discuss how the results and techniques presented in this paper can be used for studying even more expressive classes of temporal constraints.

ICAPS Conference 2011 Conference Paper

Limits for Compact Representation of Plans

• Christer Bäckström
• Peter Jonsson

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.

TCS Journal 2009 Journal Article

Hard constraint satisfaction problems have hard gaps at location 1

• Peter Jonsson
• Andrei Krokhin
• Fredrik Kuivinen

An instance of the maximum constraint satisfaction problem (Max CSP) is a finite collection of constraints on a set of variables, and the goal is to assign values to the variables that maximises the number of satisfied constraints. Max CSP captures many well-known problems (such as Max k -SAT and Max Cut) and is consequently NP-hard. Thus, it is natural to study how restrictions on the allowed constraint types (or constraint language) affect the complexity and approximability of Max CSP. The PCP theorem is equivalent to the existence of a constraint language for which Max CSP has a hard gap at location 1; i. e. it is NP-hard to distinguish between satisfiable instances and instances where at most some constant fraction of the constraints are satisfiable. All constraint languages, for which the CSP problem (i. e. , the problem of deciding whether all constraints can be satisfied) is currently known to be NP-hard, have a certain algebraic property. We prove that any constraint language with this algebraic property makes Max CSP have a hard gap at location 1 which, in particular, implies that such problems cannot have a PTAS unless P = NP. We then apply this result to Max CSP restricted to a single constraint type; this class of problems contains, for instance, Max Cut and Max DiCut. Assuming P ≠ NP, we show that such problems do not admit PTAS except in some trivial cases. Our results hold even if the number of occurrences of each variable is bounded by a constant. Finally, we give some applications of our results.

MFCS Conference 2007 Conference Paper

The Maximum Solution Problem on Graphs

• Peter Jonsson
• Gustav Nordh
• Johan Thapper

Abstract We study the complexity of the problem Max Sol which is a natural optimisation version of the graph homomorphism problem. Given a fixed target graph H with V ( H ) ⊆ ℕ, and a weight function w: V ( G ) →ℚ +, an instance of the problem is a graph G and the goal is to find a homomorphism f: G → H which maximises ∑ v ∈ G f ( v ) · w ( v ). Max Sol can be seen as a restriction of the Min Hom -problem [Gutin et al. , Disc. App. Math. , 154 (2006), pp. 881-889] and as a natural generalisation of Max Ones to larger domains. We present new tools with which we classify the complexity of Max Sol for irreflexive graphs with degree less than or equal to 2 as well as for small graphs (| V ( H )| ≤ 4). We also study an extension of Max Sol where value lists and arbitrary weights are allowed; somewhat surprisingly, this problem is polynomial-time equivalent to Min Hom.

MFCS Conference 2006 Conference Paper

Generalised Integer Programming Based on Logically Defined Relations

• Peter Jonsson
• Gustav Nordh

Abstract Many combinatorial optimisation problems can be modelled as integer linear programs. We consider a class of generalised integer programs where the constraints are allowed to be taken from a broader set of relations (instead of just being linear inequalities). The set of allowed relations is defined using a many-valued logic and the resulting class of relations have provably strong modelling properties. We give sufficient conditions for when such problems are polynomial-time solvable and we prove that they are APX -hard otherwise.

TCS Journal 2005 Journal Article

Counting models for 2SAT and 3SAT formulae

• Vilhelm Dahllöf
• Peter Jonsson
• Magnus Wahlström

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.

TCS Journal 2004 Journal Article

Algorithms for four variants of the exact satisfiability problem

• Vilhelm Dahllöf
• Peter Jonsson
• Richard Beigel

We present four polynomial space and exponential time algorithms for variants of the EXACT SATISFIABILITY problem. First, an O(1. 1120 n ) (where n is the number of variables) time algorithm for the NP-complete decision problem of EXACT 3-SATISFIABILITY, and then an O(1. 1907 n ) time algorithm for the general decision problem of EXACT SATISFIABILITY. The best previous algorithms run in O(1. 1193 n ) and O(1. 2299 n ) time, respectively. For the #P-complete problem of counting the number of models for EXACT 3-SATISFIABILITY we present an O(1. 1487 n ) time algorithm. We also present an O(1. 2190 n ) 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.

AIJ Journal 2004 Journal Article

Complexity classification in qualitative temporal constraint reasoning

• Peter Jonsson
• Andrei Krokhin

We study the computational complexity of the qualitative algebra which is a temporal constraint formalism that combines the point algebra, the point-interval algebra and Allen's interval algebra. We identify all tractable fragments and show that every other fragment is NP-complete.

TCS Journal 2004 Journal Article

Recognizing frozen variables in constraint satisfaction problems

• Peter Jonsson
• Andrei Krokhin

In constraint satisfaction problems over finite domains, some variables can be frozen, that is, they take the same value in all possible solutions. We study the complexity of the problem of recognizing frozen variables with restricted sets of constraint relations allowed in the instances. We show that the complexity of such problems is determined by certain algebraic properties of these relations. Under the assumption that NP ≠ coNP (and consequently PTIME ≠ NP ), we characterize all tractable problems, and describe large classes of NP-complete, coNP-complete, and DP-complete problems. As an application of these results, we completely classify the complexity of the problem in two cases: (1) with domain size 2; and (2) when all unary relations are present. We also give a rough classification for domain size 3.

TCS Journal 2004 Journal Article

The complexity of counting homomorphisms seen from the other side

• Víctor Dalmau
• Peter Jonsson

For every class of relational structures C, let HOM ( C, _ ) be the problem of deciding whether a structure A ∈ C has a homomorphism to a given arbitrary structure B. Grohe has proved that, under a certain complexity-theoretic assumption, HOM ( C, _ ) is solvable in polynomial time if and only if the cores of all structures in C have bounded tree-width. We prove (under a weaker complexity-theoretic assumption) that the corresponding counting problem #HOM ( C, _ ) is solvable in polynomial time if and only if all structures in C have bounded tree-width. This answers an open question posed by Grohe.

AIJ Journal 2003 Journal Article

Point algebras for temporal reasoning: Algorithms and complexity

• Mathias Broxvall
• Peter Jonsson

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.

SODA Conference 2002 Conference Paper

An algorithm for counting maximum weighted independent sets and its applications

• Vilhelm Dahllöf
• Peter Jonsson

AIJ Journal 2002 Journal Article

Disjunctions, independence, refinements

• Mathias Broxvall
• Peter Jonsson
• Jochen Renz

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.)

TIME Conference 2002 Conference Paper

Extending the Point Algebra into the Qualitative Algebra

• Andrei A. Krokhin
• Peter Jonsson

MFCS Conference 2002 Conference Paper

Finite Domain Constraint Satisfaction Using Quantum Computation

• Ola Angelsmark
• Vilhelm Dahllöf
• Peter Jonsson

Abstract We present a quantum algorithm for finite domain constraint solving, where the constraints have arity 2. It is complete and runs in \( O\left( {\left( {\left[ {d/2} \right]} \right)^{n/2} } \right) \) 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 O (8 n /8 ) ≈ O (1. 2968 n ). 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.

TCS Journal 2000 Journal Article

Boolean constraint satisfaction: complexity results for optimization problems with arbitrary weights

• Peter Jonsson

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.

ICAPS Conference 2000 Conference Paper

Planning with Reduced Operator Sets

• Patrik Haslum
• Peter Jonsson

Classical propositional STRIPSplanning 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 sometimesadverse structure of this graph. Weconjecture that the search for a plan wouldbe moreefficient if there were only a small numberof paths from the initial state to the goal state. Toverify this conjecture, we define the notion of reducedoperator sets and describe ways of finding such reduced sets. We demonstrate that somestate-of-the-art planners run faster using reduced operator sets.

AIJ Journal 2000 Journal Article

Towards efficient universal planning: A randomized approach

• Peter Jonsson
• Patrik Haslum
• Christer Bäckström

One of the most widespread approaches to reactive planning is Schoppers' universal plans. We propose a stricter definition of universal plans which guarantees a weak notion of soundness, not present in the original definition, and isolate three different types of completeness that capture different behaviors exhibited by universal plans. We show that universal plans which run in polynomial time and are of polynomial size cannot satisfy even the weakest type of completeness unless the polynomial hierarchy collapses. By relaxing either the polynomial time or the polynomial space requirement, the construction of universal plans satisfying the strongest type of completeness becomes trivial. As an alternative approach, we study randomized universal planning. By considering a randomized version of completeness and a restricted (but nontrivial) class of problems, we show that there exists randomized universal plans running in polynomial time and using polynomial space which are sound and complete for the restricted class of problems. We also report experimental results on this approach to planning, showing that the performance of a randomized planner is not easily compared to that of a deterministic planner.

AIJ Journal 1999 Journal Article

Computational complexity of relating time points with intervals

• Peter Jonsson
• Thomas Drakengren
• Christer Bäckström

Several algebras have been proposed for reasoning about qualitative constraints over the time line. One of these algebras is Vilain's point–interval algebra, which can relate time points with time intervals. Apart from being a stand-alone qualitative algebra, it is also used as a subalgebra in Meiri's approach to temporal reasoning, which combines reasoning about metric and qualitative temporal constraints over both time points and time intervals. While the satisfiability problem for the full point–interval algebra is known to be NP-complete, not much is known about its 4294967296 subclasses. This article completely determines the computational complexity of these subclasses and it identifies all of the maximal tractable subalgebras—five in total.

AIJ Journal 1998 Journal Article

A complete classification of tractability in Allen's algebra relative to subsets of basic relations

• Thomas Drakengren
• Peter Jonsson

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.

AIJ Journal 1998 Journal Article

A unifying approach to temporal constraint reasoning

• Peter Jonsson
• Christer Bäckström

We present a formalism, Disjunctive Linear Relations (DLRs), for reasoning about temporal constraints. DLRs subsume most of the formalisms for temporal constraint reasoning proposed in the literature and is therefore computationally expensive. We also present a restricted type of DLRs, Horn DLRs, which have a polynomial-time satisfiability problem. We prove that most approaches to tractable temporal constraint reasoning can be encoded as Horn DLRs, including the ORD-Horn algebra by Nebel and Bürckert and the simple temporal constraints by Dechter et al. Thus, DLRs is a suitable unifying formalism for reasoning about temporal constraints.

AIJ Journal 1998 Journal Article

State-variable planning under structural restrictions: algorithms and complexity

• Peter Jonsson
• Christer Bäckström

Computationally tractable planning problems reported in the literature so far 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. The exponential size of this graph, though, makes such restrictions costly to test. Hence, we propose an intermediate approach, using a state-variable model for planning and defining restrictions on the separate state-transition graphs for each state variable. We identify such restrictions which can tractably be tested and we present a planning algorithm which is correct and runs in polynomial time under these restrictions. The algorithm has been implemented and it outperforms Graphplan on a number of test instances. In addition, we present an exhaustive map of 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 optimal and non-optimal plan generation problem.

IJCAI Conference 1997 Conference Paper

Towards a Complete Classification of Tractability in Allen's Algebra

• Thomas Drakengren
• Peter Jonsson

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 that is not known in the literature can contain more than the three basic relations This means that concerning algebras for specifying complete knowledge about temporal informa­ tion, there is no hope of finding yet unknown classes with much expressivity. Furthermore, we show that there are exactly two maximal tractable algebras which contain the relation Both of these algebras can express the notion of sequentially; thus we have a com­ plete characterisation of tractable inference us­ ing that notion.

AIJ Journal 1997 Journal Article

Twenty-one large tractable subclasses of Allen's algebra

• Thomas Drakengren
• Peter Jonsson

This paper continues Nebel and Bürckert'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.

AAAI Conference 1996 Conference Paper

A Linear-Programming Approach to Temporal Reasoning

• Peter Jonsson

We present a new formalism, Horn Disjunctive Linear Relations (Horn DLRs), for reasoning about temporal constraints. We prove that deciding satisfiability of sets of Horn DLRs is polynomial by exhibiting an algorithm based upon linear programming. Furthermore, we prove that most other approaches to tractable temporal constraint reasoning can be encoded as Horn DLRs, including the ORD-Horn algebra and most methods for purely quantitative reasoning.

AAAI Conference 1996 Conference Paper

On the Size of Reactive Plans

• Peter Jonsson

One of the most widespread approaches to reactive planning is Schoppers’ universal plans. We propose a stricter definition of universal plans which guarantees a weak notion of soundness not present in the original definition. Furthermore, we isolate three different types of completeness which capture different behaviours exhibited by universal plans. We show that universal plans which run in polynomial time and are of polynomial size cannot satisfy even the weakest type of completeness unless the polynomial hierarchy collapses. However, by relaxing either the polynomial time or the polynomial space requirement, the construction of universal plans satisfying the strongest type of completeness becomes trivial.

AAAI Conference 1994 Conference Paper

Tractable Planning with State Variables by Exploiting Structural Restrictions

• Peter Jonsson

So far, tractable planning problems reported in the literature have been defined by syntactical restrictions. To better exploit the inherent structure in problems, however, it is probably necessary to study also structural restrictions on the state-transition graph. Such restrictions are typically computationally hard to test, though, since this graph is of exponential size. Hence, we take an intermediate approach, using a statevariable model for planning and restricting the state-transition graph implicitly by restricting the transition graph for each state variable in isolation. We identify three such restrictions which are tractable to test and we present a planning algorithm which is correct and runs in polynomial time under these restrictions.