Finitely tractable PCSPs

Abstract: The Promise Constraint Satisfaction Problem (PCSP) is a generalization of the Constraint Satisfaction Problem (CSP). In a [LICS '19] paper it was shown that a specific PCSP, the problem to find a valid Not-All-Equal solution to a 1-in-3-SAT instance, is not finitely tractable in that it can be solved by a trivial reduction to a tractable CSP, but such a CSP is necessarily over an infinite domain (unless P=NP). We further explore this phenomenon: we give a general necessary condition for finite tractability and characterize finite tractability within a class of templates - the "basic" tractable cases in the dichotomy theorem for symmetric Boolean PCSPs allowing negations by Brakensiek and Guruswami [SODA'18]. This is a joint work with Libor Barto.

category theorylogic

Audience: researchers in the topic

( paper )

PALS Panglobal Algebra and Logic Seminar

Series comments: The PALS seminar is a research and learning seminar organized by the algebra and logic research group of the Department of Mathematics at the University of Colorado at Boulder. The scope of the seminar includes all topics with links to algebra, logic, or their applications, like general algebra, logic, model theory, category theory, set theory, set-theoretic topology, or theoretical computer science. Please contact one of the organizers for the Zoom password, to join the mailing list or if you want to speak.