Promise constraint satisfaction problems

The promise constraint satisfaction problem (PCSP) is a recently introduced vast generalisation of the constraint satisfaction problem (CSP) that captures approximability of satisfiable instances. A PCSP instance comes with two forms of each constraint: a strict one and a weak one. Given the promise that a solution exists under the strict constraints, the task is to find a solution under the weak constraints. Austrin, Guruswami, and Hastad [SICOMP’17] showed that the problem of distinguishing k-CNF formulas that are g-satisfiable (some assignment satisfies at least g literals in every clause) from those that are not even 1-satisfiable is NP-hard if g/k < 1/2 and is in P otherwise. We study a generalisation of SAT on arbitrary finite domains, with clauses that are disjunctions of unary constraints, and establish analogous behaviour. Thus we give a dichotomy for a natural fragment of PCSPs on arbitrary finite domains. The hardness side is proved using the algebraic approach via a new general NP-hardness criterion on polymorphisms, which is based on a gap version of the Layered Label Cover problem. We show that previously used criteria are insufficient, and so this problem gives an interesting benchmark of algebraic techniques for proving hardness of approximation in problems such as PCSPs. Next we turn to non-symmetric PCSPs. While there now exist several dichotomy results for fragments of PCSPs, they all consider PCSPs that are symmetric in some way. 1-in-3-SAT and Not-All-Equal-3-SAT are classic examples of Boolean symmetric CSPs. While both problems are NP-hard, Brakensiek and Guruswami showed [SICOMP’21] that given a satisfiable instance of 1-in-3-SAT, one can efficiently find a solution to the corresponding instance of (weaker) Not-All-Equal-3-SAT. In other words, the PCSP template (1-in-3, NAE) is tractable. We study PCSP templates obtained from the Boolean template (t-in-k, NAE) by either adding tuples to t-in-k or removing tuples from NAE. For the former, we obtain an “algorithmic dichotomy” and classify all templates as either tractable or not solvable by one of the strongest known algorithms for PCSPs, the combined basic LP and affine IP relaxation of Brakensiek et al. [SICOMP’20]. For the latter, we classify all templates as either tractable or NP-hard. Finally, we investigate problems of the form PCSP(1-in-3, B) for B over an arbitrary finite domain. Barto, Battistelli, and Berg [STACS’21] almost completely classified such templates over domain size three, and suggested that over arbitrary domains, (1-in-3, NAE) and (1-in-3, C3) might be the only tractable templates, where C3 is a relation representing a 3-cycle. Through a connection to number theory, we exhibit an infinite family of tractable templates, of which (1-in-3, NAE) and (1-in-3, C3) are the simplest members. We conjecture that this family contains all tractable cases of PCSP(1-in-3, B), and we prove NP-hardness or non-solvability by BLP+AIP for certain PCSPs outside the family.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.