Tue, 28 Sep 2021, 1 pm MDT
For relational structures A, B, the Promise Constraint Satisfaction Problem PCSP(A, B)
asks whether a given input structure maps homomorphically to A or does not even map to B.
We are promised that the input satisfies exactly one of these two cases.
Note that if there exists C with homomorphisms A → C → B, then PCSP(A, B) reduces to CSP(C).
All known tractable PCSPs seem to reduce to tractable CSPs in this way. However Barto (2019) showed that some PCSPs over
finite structures require solving CSPs over infinite C.
We provide examples showing that even when a reduction to finite C is possible, this structure may become arbitrarily large.
This is joint work with Alexandr Kazda and Dmitriy Zhuk.