An order out of nowhere : a new algorithm for infinite-domain CSPs

We consider the problem of satisfiability of sets of constraints in a given set of finite uniform hypergraphs. While the problem under consideration is similar in nature to the problem of satisfiability of constraints in graphs, the classical complexity reduction to finite-domain CSPs that was used in the proof of the complexity dichotomy for such problems cannot be used as a black box in our case. We therefore introduce an algorithmic technique inspired by classical notions from the theory of finite-domain CSPs, and prove its correctness based on symmetries that depend on a linear order that is external to the structures under consideration. Our second main result is a P/NP-complete complexity dichotomy for such problems over many sets of uniform hypergraphs. The proof is based on the translation of the problem into the framework of constraint satisfaction problems (CSPs) over infinite uniform hypergraphs. Our result confirms in particular the Bodirsky-Pinsker conjecture for CSPs of first-order reducts of some homogeneous hypergraphs. This forms a vast generalization of previous work by Bodirsky-Pinsker (STOC’11) and Bodirsky-Martin-Pinsker-Pongrácz (ICALP’16) on graph satisfiability.

Subjects

Constraint Satisfaction Problems

Hypergraphs

Polymorphisms

DDC Class

004: Computer Sciences

Publication version

publishedVersion

Lizenz

https://creativecommons.org/licenses/by/4.0/

Name

LIPIcs.ICALP.2024.148.pdf

Type

Main Article

Size

749.52 KB

Format

Adobe PDF

Options

An order out of nowhere : a new algorithm for infinite-domain CSPs