Seminar: Expressibility of constraint satisfaction problems with Maltsev templates in extensions of first-order logic
- Date
- February 05, 2020
- Time
- 11:00 AM EST - 12:00 PM EST
- Location
- ENG-210
- Open To
- All Faculty, staff, students and guests are welcome to attend
One of the fundamental open problems in the field of nite model theory and, specifically, descriptive complexity is the question whether there exists a logic which characterizes polynomial time on the class of nite relational structures. One of the prominent candidates in this quest is the logic of Choiceless Polynomial Time (CPT) (with or without counting). Work presented by Gradel, Pakusa and Schalthofer has shown that the mechanism of CPT can be replaced by a more standard model-theoretic construction of iterated first-order interpretations, along with the counting mechanism provided by Hartig quantifiers.
In this talk, I will show that constraint satisfaction problems over Maltsev templates can be expressed in the logic PIL+H.
This is joint work with Dr. Dejan Delic.
