Manuel Bodirsky

The Status of the 19 Open Problems posed in my PhD-thesis

In my PhD-thesis in 2004, I posed 19 questions related to the complexity of infinite-domain constraint satisfaction; 16 remain open. Here is a report about progress on these problems. More background for the problems mentioned here can be found in Section 7.4 of my thesis.

Question 1: Temporal Reasoning

Which structures that are interpretable in the dense linear order of the rational numbers (Q,<) have tractable constraint satisfaction problems?

Status is still open. If interpretable is replaced by definable (by which I mean first-order definable without parameters) the problem has been solved. Note that all finite structures are interpretable in every structure with more than one element, so a solution would also yield a description of the tractable CSPs over finite domains.

Question 2: Tree Description Languages

Which structures interpretable in the omega-categorical, unbounded, dense, and binary branching semilinear order have tractable constraint satisfaction problems?

This is open even if 'interpretable' is replaced by 'definable'. Already there we find many concrete problems that have been studied independently in artificial intelligence ('branching time constrains'), computational biology ('phylogenetic reconstruction'), and computational linguistics ('tree description constraints').

Question 3: Universal Algebra

What are the polymorphisms of the structure with all binary relations that are first-oder definable the semi-linear order described in Question 2?

Open. (The formulation is slightly different from the version in my thesis to make it more clear.)

Question 4: Model Theory

Let N be a finite set of relational structures, and let Forb(N) be the set of all finite structures that do not embed a structure from N. When is Forb(N) an amalgamation class?

Open.

Question 5: Monotone SNP

Let Q be a set of structures that is closed under taking disjoint unions. Is it true that Q is in monotone SNP if and only if it can be described as CSP(Gamma) where Gamma is a finitely constrained omega-categorical structure?

Trivially false: CSP(Z,succ), where succ is the binary successor relation over the integers, cannot be formulated with an omega-categorical template (see On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction) but is clearly in monotone SNP.

Question 6: Decidability of Primitive Positive Definability

Let Gamma be a finitely constrained homogeneous tau-structure. Given a first-order formula over signature tau, is it decidable whether the formula is on Gamma equivalent to a primitive positive formula?

Open in general. But strong partial results can be found in Decidability of Definability.

Question 7: Infinite Constraint Languages

Is there a constraint satisfaction problem with an omega-categorical template which is tractable, but not globally tractable?

To entirely formalize this question, one would have to specify how to represent the relations from the infinite signature in the input. The formulation in the thesis by mistake also requires that Gamma is finitely constrained. What was actually meant is that all relations of Gamma are first-order definable over some finitely constrained homogeneous structure with the same domain. For such structures there is a natural representation for the relations in the input. The question is still open for those structures.

Question 8: Model Theory

For which sets N of finite graphs (or, more generally, structures over a finite signature) the almost-sure theory of Forb(N) is omega-categorical?

Open as far as I know.

Question 9: Datalog

Let N be a finite set of finite structures such that Forb(N) is an amalgamation class, and let Gamma be its Fraisse-limit. Is it decidable whether CSP(Gamma) has width k, or bounded width?

Open.

Question 10: Datalog

Is there an omega-categorical CSP which has bounded width k for k larger than 2, but does not have width 2?

Yes (to appear).

Question 11: Universal Algebra

Given a finitely constrained omega-categorical structure Gamma, is it decidable whether CSP(Gamma) has bounded strict width?

Even though a universal-algebraic characterization of bounded strict width exists (also see these applications) its decidability is still open. However, using this in combination with Decidability of Definability we get decidability in many cases.

Question 12: Datalog

Is 'Consistent Genealogy', i.e., the CSP for the binary relations definable in the unbounded dense semilinear ordering, solvable by Datalog?

Solved: the answer is negative, see Rooted Phylogeny Problems.

Question 13: Universal Algebra

Let Gamma be an omega-categorical structure with a finite relational signature, where Pol(Gamma) contains a Maltsev operation. Is CSP(Gamma) tractable?

Solved: if Gamma has a Maltsev polymorphism (actually, a quasi Maltsev suffices), then its model-complete core also has a quasi-Maltsev operation. But, as shown in this paper, the model-complete core of such a structure must be finite, so the CSP is in P by the algorithm of Bulatov and Dalmau.

Question 14: Complexity Classification

For which MMSNP(\neq)-sentences on graphs the model-checking problem is NP-hard?

This is un undecidable property so we cannot hope for an answer here.

Question 15: Complexity Classification

Let H be an infinite graph. Is it true that CSP(H) is either in P or NP-hard?

For directed graphs, the answer is no (and for undirected graphs I strongly conjecture that it is false as well).

Question 16: Complexity Classification

Is every surjective homomorphism problem computationally equivalent to a finitely constrained CSP?

Open.

Question 17: Complexity Classification

Which finite structures have tractable surjective homomorphism problems?

Open, probably very difficult. The first problems of open computational complexity appear for domain size three (see below). But this problem is also open for the six-cycle (an undirected graph).

Question 18: Combinatorics

Is the 3-partition problem NP-hard?

Open. The 3-partition problem asks whether we can find for a given ternary relation R on a finite set V a partition of V into three non-empty sets A,B,C such that for every tuple (x,y,z) from R either x,y,z lie in the same part, or x is from A, y is from B, and z is from C.

Question 19: Combinatorics

Is the no-rainbow-coloring problem NP-hard?

Open. The no-rainbow problem asks whether a given 3-uniform hypergraph on vertex set V can be partitioned into three non-empty subsets A,B,C of V such that no edge is 'rainbow-colored', i.e., contains one vertex from each of A,B,C.