Fine-Grained Complexity of Constraint Satisfaction Problems through Partial Polymorphisms: A Survey (Dedicated to the memory of Professor Ivo Rosenberg)

Abstract : Constraint satisfaction problems (CSPs) are combi-natorial problems with strong ties to universal algebra and clone theory. The recently proved CSP dichotomy theorem states that finite-domain CSPs are always either tractable or NP-complete. However, among the intractable cases there is a seemingly large variance in complexity, which cannot be explained by the classical algebraic approach using polymorphisms. In this contribution we will survey an alternative approach based on partial polymorphisms, which is useful for studying the fine-grained complexity of NP-complete CSPs. Moreover, we will state some challenging open problems in the research field.
Document type :
Conference papers
Complete list of metadatas

Cited literature [42 references]  Display  Hide  Download

https://hal.inria.fr/hal-02190089
Contributor : Miguel Couceiro <>
Submitted on : Sunday, July 21, 2019 - 11:45:12 PM
Last modification on : Wednesday, August 28, 2019 - 3:10:42 PM

File

survey_paper_ismvl-REV.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02190089, version 1

Collections

Citation

Miguel Couceiro, Lucien Haddad, Victor Lagerkvist. Fine-Grained Complexity of Constraint Satisfaction Problems through Partial Polymorphisms: A Survey (Dedicated to the memory of Professor Ivo Rosenberg). ISMVL2019 - IEEE 49th International Symposium on Multiple-Valued Logic, May 2019, Fredericton, NB, Canada. ⟨hal-02190089⟩

Share

Metrics

Record views

45

Files downloads

367