We propose a new algorithm for Promise Constraint Satisfaction Problems (PCSPs). It is a combination of the Constraint Basic LP relaxation and the Affine IP 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 and Guruswami [SODA'20] and not by a reduction to tractable finite-domain CSPs.
翻译：我们提出了一个新的承诺约束性满意度问题算法(PCSPs ) 。 这是限制性基本 LP 放松和缩写 IP 放松(CLAP ) 的结合。 我们用迷你式同质主义来描述CLAP的力量。 使用这种特征,我们找出了某种较弱的对称概念, 如果被无限多的PCSP的多种形态所满足, 就能保证可移动性。 我们证明有些由CLAP解决的PCSP没有被PCSP的任何现有算法所解决, 特别是没有被Brakesiek和Guruswami的BLP+AIP算法(SODA'20)所解决, 而不是被削减为可移植的有限域 CSPs 。
相关内容
微信扫码咨询专知VIP会员