Algebra Seminar talk
13:30
Kristina Asimi
(Not) Finitely Tractable PCSPs
Abstract:
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).