the promised open problems

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
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
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
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
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
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.

Problem
Characterise f.o.-definable PCSPs.

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
Does every PCSP that is f.o.-definable have finite duality? If not, characterise PCSPs that have finite duality.

PCSPs also brought new algorithms that make good sense for CSPs. Notably, all tractable results on PCSPs are either trivial lifts from CSPs (homomorphic relaxations of tractable finite template CSPs), or are solvable by an algorithm that combines LP and solving affine equations over integers. The power of this algorithm has been classified by the means of minor identities in [11]. This is an algorithm that can be also used in the CSP setting. A particularly interesting question, that has been formulated in [11], is whether a strengthening of this algorithm by replacing the first step with a higher-level Sherali-Adams can be used as a universal algorithm for tractable CSPs (i.e., as a replacement of Bulatov’s and Zhuk’s algorithms). At my talk at AAA 100, I have conjectured that the answer to this question is positive and offered a prize of a bottle of fine single malt Scotch whisky for anybody who proves me wrong, and provides a finite template CSP that cannot be solved by this algorithm.

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

  1. Austrin, P., Guruswami, V., and Håstad, J. (2017). (2 + ϵ)-Sat is NP-hard. SIAMJ. 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.11453313276.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.11371.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.11371.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.11371.9781611975031.117 [return]
  10. Atserias, A., Dalmau, V. (2021). Promise Constraint Satisfaction and Width. https://arxiv.org/abs/2107.05886 [return]
  11. 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]