# 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).