×
Brandts, Alex; Wrochna, Marcin; Živný, Stanislav

The complexity of promise SAT on non-Boolean domains. (English) Zbl 1495.68157

ACM Trans. Comput. Theory 13, No. 4, Article No. 26, 20 p. (2021).

Cited in 5 Documents

MSC:

68R07 Computational aspects of satisfiability
08A70 Applications of universal algebra in computer science
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity

Keywords:

promise constraint satisfaction; PCSP; polymorphisms; algebraic approach; label cover

Citations:

Zbl 1476.68188
Cite Review PDF
Full Text: DOI arXiv