We propose a new algorithm for Promise Constraint Satisfaction Problems PCSPs). It is a combination of the $\textbf{C}$onstraint Basic $\textbf{L}$P relaxation and the $\textbf{A}$ffine I$\textbf{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.
翻译:我们为承诺约束性满意度问题PCSP提出了一个新的算法。 它是一个组合, 包括$\ textbf{C}$A}$pressimate Basic $\ textbf{L}$P 放松与$\ textbf{A}$ffine I$fine I$\ textbf{P}$放松 (CLAP) 的组合。 我们用迷你同质性来描述CLAP的力量。 使用此特性, 我们发现一个比较弱的对称概念, 如果符合PCSP的无限多形态, 就能保证可移动性。 我们证明有CLAP解决的PCSP没有被PCSP的任何现有算法解决, 特别是没有被Brakesik 等人的 BLP+AIP算法解决 。 [SICOMP'20] 而不是被降低可移植的有限多域 CSPs 。