Algebra Seminar talk
(Not) Finitely Tractable PCSPs
Promise Constraint Satisfaction Problem (PCSP) is a generalization of Constraint Satisfaction Problem (CSP). All the currently known tractable (i.e., solvable in polynomial time) PCSPs over finite templates can be reduced to tractable CSPs. I present some classes of PCSPs for which that CSP has to be over an infinite domain (unless P=NP).