CLAP: A NEW ALGORITHM FOR PROMISE CSPS\ast

被引：10
作者：
Ciardo, Lorenzo [1 ]
Zivny, Stanislav [1 ]
机构：
[1] Univ Oxford, Dept Comp Sci, Wolfson Bldg, Parks Rd, Oxford OX1 3QD, England
来源：
SIAM JOURNAL ON COMPUTING | 2023年 / 52卷 / 01期
基金：
欧洲研究理事会;
关键词：
promise constraint satisfaction; homomorphism problems; linear programming; CONSTRAINT SATISFACTION; ALGEBRAIC STRUCTURE; ARC CONSISTENCY; COMPLEXITY; HARDNESS; POWER;
D O I：
10.1137/22M1476435
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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 characterization of the power of CLAP in terms of a minion homomorphism. Using this characterization, 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. [SIAM J. Comput., 49 (2020), pp. 1232--1248] and not by a reduction to tractable finite-domain CSPs.
引用
收藏
页码：1 / 37
页数：37
相关论文
共 71 条
  • [1] [Anonymous], 1978, P 10 ANN ACM S THEOR, DOI DOI 10.1145/800133.804350
  • [2] Proof verification and the hardness of approximation problems
    Arora, S
    Lund, C
    Motwani, R
    Sudan, M
    Szegedy, M
    [J]. JOURNAL OF THE ACM, 1998, 45 (03) : 501 - 555
  • [3] Probabilistic checking of proofs: A new characterization of NP
    Arora, S
    Safra, S
    [J]. JOURNAL OF THE ACM, 1998, 45 (01) : 70 - 122
  • [4] Atserias A, 2022, PROCEEDINGS OF THE 2022 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, P1129
  • [5] Austrin P, 2020, PROCEEDINGS OF THE THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'20), P1479
  • [6] (2+ε)-SAT IS NP-HARD
    Austrin, Per
    Guruswami, Venkatesan
    Hastad, Johan
    [J]. SIAM JOURNAL ON COMPUTING, 2017, 46 (05) : 1554 - 1573
  • [7] BARTO L., 2017, Dagstuhl Follow-Ups, V7, P1, DOI [10.4230/DFU.Vol7.15301.1, DOI 10.4230/DFU.VOL7.15301.1]
  • [8] Algebraic Approach to Promise Constraint Satisfaction
    Barto, Libor
    Bulin, Jakub
    Krokhin, Andrei
    Oprsal, Jakub
    [J]. JOURNAL OF THE ACM, 2021, 68 (04)
  • [9] Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case
    Barto, Libor
    Battistelli, Diego
    Berg, Kevin M.
    [J]. 38TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2021), 2021, 187
  • [10] TOPOLOGY IS IRRELEVANT (IN A DICHOTOMY CONJECTURE FOR INFINITE DOMAIN CONSTRAINT SATISFACTION PROBLEMS)
    Barto, Libor
    Pinsker, Michael
    [J]. SIAM JOURNAL ON COMPUTING, 2020, 49 (02) : 365 - 393
12345678