Česky | English Sign in

Our Events - SIAM SC Seminar - Other Events

(Not) Finitely Tractable PCSPs

Date: 13/04/2022 15:40 - 13/04/2022 17:10
Place: Seminar room KNM (K433KNM)
We cordially invite you to our next SIAM SC seminar. The talk will be given by Kristina Asimi. See the abstract and poster below:

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. We present some classes of PCSPs for which that CSP has to be over an infinite domain (unless P=NP).

poster