Algebra Seminar talk
2024-10-25
Christoph Spiess
Omega-categorical sandwiches for Promise Constraint Satisfaction Problems
Abstract:
For given finite structures A,B such that A maps homomorphically to B, denoted A->B, PCSP(A,B) asks whether a given finite structure X satisfies X->A or does not even map homomorphically to B. It is promised that all input structures satisfy one of these two cases. A powerful approach to investigating the computational complexity of PCSPs is the sandwiching method: If there is some structure C such that A->C->B, then PCSP(A,B) reduces to CSP(C). Such C is called a sandwich structure for (A,B).
In this talk, I will provide an example of a pair (C,B) with a tractable omega-categorical structure C and a finite structure B with C->B such that the CSP of every finite B' with C->B'->B is NP-complete. This provides the potential "right side" of a PCSP that admits a tractable omega-categorical sandwich structure but no finite tractable sandwich.