FO-Definable Constraint Satisfaction Problems
summary
Decision: for any finite template T, satisfiability of FO-definable instances over atoms with equality is decidable (via orbit-constant homomorphisms); key lemma replaces arbitrary homomorphisms by ones constant on orbits under monotone atom permutations. Proof uses Ramsey/topological dynamics and yields at most exponential blowup in complexity (e.g. 3-colorability lifts to NEXP-complete). Allowing a definable template reduces to a finite-template case, but allowing arbitrary definable signature makes the problem undecidable; isomorphism remains open.
AI-written summary · about