Orbit-finite Constraint Satisfaction Problems

We study extensions of the classical Constraint Satisfaction Problem, to the orbit-finite setting. In one direction, we allow the instances to be orbit-finite, while preserving a finite template. We show that the problem remains decidable (where orbit-finite instances are represented by formulas), and we provide tight complexity bounds. In another direction, we extend the classical setting by keeping the instances finite and allowing the templates to be orbit-finite over an orbit-finite signature, which consists of finite relations. We show that most of the classical complexity results lift to this setting.