Charles University Chapter of SIAM

Naše akce - Seminář SIAM SC - Další akce

(Not) Finitely Tractable PCSPs

Kdy: 13/04/2022 15:40 - 13/04/2022 17:10
Kde: 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