Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem
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
2021-02-102021-02-102022-11-18Bibliographically approved