Solving small PCSPs via large CSPs

Abstract: For relational structures A, B, the Promise Constraint Satisfaction Problem PCSP(A, B) asks whether a given input structure maps homomorphically to A or does not even map to B. We are promised that the input satisfies exactly one of these two cases. Note that if there exists C with homomorphisms A → C → B, then PCSP(A, B) reduces to CSP(C). All known tractable PCSPs seem to reduce to tractable CSPs in this way. However Barto (2019) showed that some PCSPs over finite structures require solving CSPs over infinite C. We provide examples showing that even when a reduction to finite C is possible, this structure may become arbitrarily large. This is joint work with Alexandr Kazda and Dmitriy Zhuk.

computational complexitycategory 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.