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

Direct link
Cite
Citation style
  • apa
  • 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
Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
2021 (English)In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 117, p. 23-39Article in journal (Refereed) Published
Abstract [en]

The inverse satisfiability problem over a set of relations Gamma (INv-SAT(Gamma)) is the problem of deciding whether a relation R can be defined as the set of models of a SAT(Gamma) instance. Kavvadias and Sideri (1998) [15] obtained a dichotomy between P and co-NP-complete for finite r containing the two constant Boolean relations. However, for arbitrary constraint languages the complexity has been wide open, and in this article we finally prove a complete dichotomy theorem for finite languages. Kavvadias and Sideris techniques are not applicable and we have to turn to the more recent algebraic approach based on partial polymorphisms. We also study the complexity of the inverse constraint satisfaction problem prove a general hardness result, which in particular resolves the complexity of INvERSE k-COLOURING, mentioned as an open problem in Chen (2008) [8]. (C) 2020 Elsevier Inc. All rights reserved.

Place, publisher, year, edition, pages
Elsevier, 2021. Vol. 117, p. 23-39
Keywords [en]
Clone theory; Universal algebra; Satisfiability problems; Constraint satisfaction problems; Inverse problems
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-173173DOI: 10.1016/j.jcss.2020.10.004ISI: 000606822100002OAI: oai:DiVA.org:liu-173173DiVA, id: diva2:1527428
Conference
46th International Colloquium on Automata, Languages and Programming (ICALP), Patras, GREECE, jul 09-12, 2019
Note

Funding Agencies|German Research Foundation (DFG)German Research Foundation (DFG) [622397]; Swedish Research Council (VR)Swedish Research Council [2019-03690]; National Graduate School in Computer Science(CUGS), Sweden

Available from: 2021-02-10 Created: 2021-02-10 Last updated: 2022-11-18Bibliographically approved

Open Access in DiVA

fulltext(532 kB)130 downloads
File information
File name FULLTEXT01.pdfFile size 532 kBChecksum SHA-512
e5eada7cf4b581b318487b9a304ba631c37d7ac15d871086f9f114bbc1fff97138238b2ba80b9dd2e349ddeca926e3087090a77431d7906c7eb288aa2d3e971d
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Authority records

Lagerkvist, VictorRoy, Biman

Search in DiVA

By author/editor
Lagerkvist, VictorRoy, Biman
By organisation
Software and SystemsFaculty of Science & Engineering
In the same journal
Journal of computer and system sciences (Print)
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 130 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • 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