liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Fine-Grained Complexity of Constraint Satisfaction Problems through Partial Polymorphisms: A Survey
Univ Lorraine, France.
Royal Mil Coll Canada, Canada.
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
2019 (English)In: 2019 IEEE 49TH INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC (ISMVL), IEEE , 2019, p. 170-175Conference paper, Published paper (Refereed)
Abstract [en]

Constraint satisfaction problems (CSPs) are combinatorial 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.

Place, publisher, year, edition, pages
IEEE , 2019. p. 170-175
Series
International Symposium on Multiple-Valued Logic, ISSN 0195-623X
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-160635DOI: 10.1109/ISMVL.2019.00037ISI: 000484992100029ISBN: 978-1-7281-0092-0 (print)OAI: oai:DiVA.org:liu-160635DiVA, id: diva2:1360186
Conference
49th IEEE International Symposium on Multiple-Valued Logic (ISMVL)
Available from: 2019-10-11 Created: 2019-10-11 Last updated: 2019-10-11

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Search in DiVA

By author/editor
Lagerkvist, Victor
By organisation
Software and SystemsFaculty of Science & Engineering
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 6 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf