Orbit-finite Constraint Satisfaction Problems

Prelegent(ci)

Szymon Toruńczyk

Afiliacja

Uniwersytet Warszawski

Termin

11 lutego 2015 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Joanna Ochremiak, Bartek Klin and Eryk Kopczyński

Seminarium

Seminarium „Teoria automatów”

---

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.

---