Affine Consistency and the Complexity of Semilinear Constraints

Johan Thapper ( Université Paris-Est, Marne-la-Vallée )

The linear programming feasibility problem can be expressed as an infinite-domain constraint satisfaction problem over the rationals in which the allowed constraint relations are (1) the unary constant 1-relation, (2) the binary linear order relation, and (3) the ternary addition relation stating that x+y=z. It is then possible to look for tractable extensions of the linear programming feasibility problem by allowing additional relations from some larger family. In Bodirsky et al. [LMCS, 2012], this idea was explored for the addition of semilinear relations. It turns out that tractability is maintained under the addition of any finite number of such relations as long as they are "essentially convex".

We extend these ideas by investigating what happens when one does not necessarily allow the full power of linear programming feasibility. More specifically, we look at constraint satisfaction problems allowing the ternary addition relation x+y=z together with an arbitrary finite set of semilinear relations. For a large subclass of these problems, we identify the boundary between tractable and hard problems. To handle the new tractable problems, we introduce a notion of affine consistency and an accompanying algorithm which in favourable cases computes the affine hull of the set of satisfying assignments, and hence can be used to decide satisfiability.