The promised open problems

3 Jan 2021

This note is a list of open problems and ideas for research directions in and around promise constraint satisfaction problems. It is certainly not an exhaustive list of open problems that I personally find interesting, or I believe they will open interesting further directions. I hope it will be useful nevertheless.

Let me first start with the definition of a promise constraint satisfaction problem with a given template.

Definition

A promise template is a pair of relational structures A, B such that A maps homomorphically to B (the two structures have the same signature). The goal of search variant of the promise constraint satisfaction problem with template A, B, denoted by PCSP(A, B), is: given a structure I which maps to A, find a homomorphism from I to B.

PCSP has also a decision variant which is a promise decision problem where the goal is to decide between instances that map to A and those that do not map to B. Obviously, decision is never harder then search, but it is currently not known whether there is an efficient way to find a solution if we are given a decision procedure.

Problem 1
Does search always belong to the same complexity class as decision?

Complexity of concrete templates

Most current papers focus on complexity of a certain problem, or a class of problems. This started with the paper [1] that classified complexity of a version of promise-SAT. Notable directions are:

An interesting framework to work with in this direction is to fix a structure A, and aim at classifying how complexity of PCSP(A, B) depends on B. This can be seen as investigation of a certain type of approximation for CSP(A) making it interesting for wider audience as long as CSP(A) is an interesting problem: in particular if A is the 3-clique graph, then this is approximate graph colouring.

Problem 2
Fix A, classify how the complexity of PCSP(A, B) depends on B.

This classification has been achieved in the case when A is the Boolean not-all-equal [7], but, as far as I know, there is a limited progress in any other non-trivial cases. Depending on the structure A, this can bring interesting insights: see for example the recent paper that partially resolves the case when A is the 1-in-3-SAT template [8]. For completeness, we include the conjecture that is attributed to Brakensiek and Guruswami [9].

Conjecture 3
PCSP(G, H) is NP-hard if G and H are both non-bipartite loop-less unoriented graphs.

The power of algorithms

Classifying the power of certain algorithms in the scope of finite template CSPs is one of the strength of the algebraic approach to CSP. Naturally, we would like to extend known classification to PCSPs for algorithms that apply in this case. An algorithm that makes very good sense in the PCSP setting is local consistency checking (‘the bounded width algorithm’). This is essentially the same algorithm as for CSPs: to use it to solve PCSP(A, B), run the local consistency algorithm on the instance as an instance of CSP(A). The question here is whether each instance that is consistent as an instance of CSP(A) is solvable as an instance of CSP(B).

Problem 4
Characterise all finite template PCSPs solvable by local consistency.

Local consistency has also a stronger version using LP, called Sherali-Adams, though for finite template CSPs these Sherali-Adams has the same power as local-consistency (every CSP solvable by SA is solvable by consistency). There is no obvious reason why this should be also true for PCSPs.

Problem 5
Is there a finite PCSP template A, B which is solvable by some level of Sherali-Adams but it is not solvable by local consistency?

Such a template was provided by Atserias and Dalmau [10]: PCSP(1-in-3, NAE-3) is not solvable by any level of local consistency while it is solvable by the second level of Sherali-Adams.

For the next problem, we have to say what we mean by PCSP being definable in some logic. We phrase it for first order definability, but it makes sense for other logics as well. Note that PCSP(A, B) is defined by two sets: the set of all positive instances (i.e., structures that map to A), and the set of all negative instances (i.e., structures that do not map to B). We say that a PCSP is defined by a f.o.-formula ϕ if all structures that map to A satisfy ϕ, and all structures that do not map to B fail to satisfy ϕ. In other words, a PCSP is f.o.-definable if there is a f.o.-formula that is true on all the yes-instances and false on all the no-instances.

For finite template CSPs, it is well-known that any fo-definable CSP has finite duality. With a bit of care, finite duality can be generalised to PCSPs: Loosely speaking for a promise template A, B to have ‘finite duality’, we do not a finite set of structures that do not map to A (called obstructions) that witness all the no-instances, i.e., for every I that does not map to B, one of the obstructions maps to I.

Problem 6
Characterise f.o.-definable PCSPs.
Problem 7
Does every PCSP that is f.o.-definable have finite duality? If not, characterise PCSPs that have finite duality.

These two problems have been solved by Antoine Mottet [11] who shows that a PCSP is f.o.-definable if and only if it has finite duality if and only if it sandwiches a finite template CSP with finite duality.

Since some of the classical CSP algorithms, e.g., the Maltsev or few subpowers algorithms, cannot be applied to the promise setting due to lack of composition, there are several new algorithms that go beyond local consistency and solving systems of affine equations. A few of these algorithms are strong enough to solve all finite template CSPs that are either affine (e.g., systems of equations over finite fields) or of bounded width (i.e., solvable by local consistency). These include the following three algorithms as well as an algorithm called CLAP described in [12].

The first algorithm is a variation on an algorithm classified by [13]: it is a combination LP and AIP. I conjecture that the algorithm obtained from that by replacing LP with some level of Sherali-Adams solves all tractable finite CSPs (assuming P ≠ NP).

Conjecture 8
Every finite template CSP with a Siggers polymorphism solvable by some level of Sherali-Adams combined with solving affine equations over integers.

The second algorithm is slightly weaker, but more combinatorial. It can be described as replacing Sherali-Adams in the above algorithm with k-consistency. A proper formalisation is given in [14, Definition 5.24]; the algorithm in this definition is more general allowing to solve the final system of equations over a cyclic group and the algorithm is called k-consistency reduction to group equations.

Conjecture 9 [14, Conjecture 5.16]
For every finite CSP template A with a Siggers polymorphism, there is a k such that CSP(A) is solved by the k-consistency reduction to integer equations.

A similar, but stronger algorithm was described by Adam Ó Conghaile [15] who named it cohomological k-consistency.

Conjecture 10
For every finite CSP template A with a Siggers polymorphism, there is a k such that CSP(A) is solved by the cohomological k-consistency.

I offered a prize of a bottle of fine single malt Scotch whisky for anybody who disproves any of these three conjectures, i.e., provides a finite template with a Siggers with a prove that it is not solved by k-consistency together with AIP for any k.

  1. Austrin, P., Guruswami, V., and Håstad, J. (2017). (2 + ϵ)-Sat is NP-hard. SIAM J. Comput., 46(5), 1554–1573. https://doi.org/10.1137/15M1006507 [return]
  2. Ficak, M., Kozik, M., Olšák, M., and Stankiewicz, S. (2019). Dichotomy for symmetric Boolean PCSPs. In C. Baier, I. Chatzigiannakis, P. Flocchini, and S. Leonardi (Eds.), 46th international colloquium on automata, languages, and programming (ICALP 2019) (Vol. 132, pp. 57:1–57:12). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2019.57 [return]
  3. Bulín, J., Krokhin, A., and Opršal, J. (2019). Algebraic approach to promise constraint satisfaction. Proceedings of the 51st Annual ACM SIGACT Symposium on the Theory of Computing (STOC ’19), 602–613. https://doi.org/10.1145⁄3313276.3316300 [return]
  4. Wrochna, M., and Živný, S. (2020). Improved hardness for H-colourings of G-colourable graphs. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’20), 1426–1435. https://doi.org/10.1137⁄1.9781611975994.86 [return]
  5. Austrin, P., Bhangale, A., and Potukuchi, A. (2020). Improved inapproximability of rainbow coloring. Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’20), 1479–1495. https://doi.org/10.1137⁄1.9781611975994.90 [return]
  6. Guruswami, V., and Sandeep, S. (2020). d-to-1 hardness of coloring 3-colorable graphs with O(1) colors. In A. Czumaj, A. Dawar, and E. Merelli (Eds.), 47th international colloquium on automata, languages, and programming (ICALP 2020) (Vol. 168, pp. 62:1–62:12). Schloss Dagstuhl–Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2020.62 [return]
  7. Dinur, I., Regev, O., and Smyth, C. (2005). The hardness of 3-uniform hypergraph coloring. Combinatorica, 25(5), 519–535. https://doi.org/10.1007/s00493-005-0032-4 [return]
  8. Barto, L., Battistelli, D., and Berg, K. M. (2021). Symmetric promise constraint satisfaction problems: Beyond the boolean case. STACS 2021. https://arxiv.org/abs/2010.04623 [return]
  9. Brakensiek, J., and Guruswami, V. (2018). Promise constraint satisfaction: Structure theory and a symmetric boolean dichotomy. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1782–1801. https://doi.org/10.1137⁄1.9781611975031.117 [return]
  10. Atserias, A., Dalmau, V. (2021). Promise Constraint Satisfaction and Width. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1129–1153. https://doi.org/10.1137⁄1.9781611977073.48 https://arxiv.org/abs/2107.05886 [return]
  11. Mottet, A. (2022), Promise constraints and cheese, talk at Dagstuhl seminar 22201, 20 May 2022. [return]
  12. Ciardo, L., and Živný, S. (2022). CLAP: A New Algorithm for Promise CSPs. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’22). 1057–1068. https://doi.org/10.1137⁄1.9781611977073.46 [return]
  13. Brakensiek, J., Guruswami, V., Wrochna, M., and Živný, S. (2020). The power of the combined basic LP and affine relaxation for promise CSPs. https://arxiv.org/abs/1907.04383v3 [return]
  14. Dalmau, V., and Opršal, J. (2023). Local consistency as a reduction between constraint satisfaction problems. https://arxiv.org/abs/2301.05084 [return]
  15. Ó Conghaile, A. (2022). Cohomology in Constraint Satisfaction and Structure Isomorphism. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). https://doi.org/10.4230/LIPIcs.MFCS.2022.75 [return]