CLAP: A New Algorithm for Promise CSPs

Abstract

We propose a new algorithm for Promise Constraint Satisfaction Problems PCSPs). It is a combination of the $\text{C}$onstraint Basic $\text{L}$P relaxation and the $\text{A}$ffine I$\text{P}$ relaxation (CLAP). We give a characterisation of the power of CLAP in terms of a minion homomorphism. Using this characterisation, we identify a certain weak notion of symmetry which, if satisfied by infinitely many polymorphisms of PCSPs, guarantees tractability. We demonstrate that there are PCSPs solved by CLAP that are not solved by any of the existing algorithms for PCSPs; in particular, not by the BLP+AIP algorithm of Brakensiek et al. [SICOMP'20] and not by a reduction to tractable finite-domain CSPs.

Full version of a SODA 2022 paper

References in corpus (2)

• Conditional Dichotomy of Boolean Ordered Promise CSPs
• Beyond PCSP (1-in-3,NAE)

Cited by in corpus (6)

• On the complexity of symmetric vs. functional PCSPs
• Injective hardness condition for PCSPs
• Approximate Graph Colouring and the Crystal with a Hollow Shadow
• Solving promise equations over monoids and groups
• 1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
• Hierarchies of Minion Tests for PCSPs through Tensors