Change search
ReferencesLink to record
Permanent link

Direct link
Strong Partial Clones and the Complexity of Constraint Satisfaction Problems: Limitations and Applications
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering. (TCSLAB)
2016 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

In this thesis we study the worst-case time complexity of the constraint satisfaction problem parameterized by a constraint language (CSP(S)), which is the problem of determining whether a conjunctive formula over S has a model. To study the complexity of CSP(S) we borrow methods from universal algebra. In particular, we consider algebras of partial functions, called strong partial clones. This algebraic approach allows us to obtain a more nuanced view of the complexity CSP(S) than possible with algebras of total functions, clones.

The results of this thesis is split into two main parts. In the first part we investigate properties of strong partial clones, beginning with a classification of weak bases for all Boolean relational clones. Weak bases are constraint languages where the corresponding strong partial clones in a certain sense are extraordinarily large, and they provide a rich amount of information regarding the complexity of the corresponding CSP problems. We then proceed by classifying the Boolean relational clones according to whether it is possible to represent every relation by a conjunctive, logical formula over the weak base without needing more than a polynomial number of existentially quantified variables. A relational clone satisfying this condition is called polynomially closed and we show that this property has a close relationship with the concept of few subpowers. Using this classification we prove that a strong partial clone is of infinite order if (1) the total functions in the strong partial clone are essentially unary and (2) the corresponding constraint language is finite. Despite this, we prove that these strong partial clones can be succinctly represented with finite sets of partial functions, bounded bases, by considering stronger notions of closure than functional composition.

In the second part of this thesis we apply the theory developed in the first part. We begin by studying the complexity of CSP(S) where S is a Boolean constraint language, the generalised satisfiability problem (SAT(S)). Using weak bases we prove that there exists a relation R such that SAT({R}) is the easiest NP-complete SAT(S) problem. We rule out the possibility that SAT({R}) is solvable in subexponential time unless a well-known complexity theoretical conjecture, the exponential-time hypothesis, (ETH) is false. We then proceed to study the computational complexity of two optimisation variants of the SAT(S) problem: the maximum ones problem over a Boolean constraint language S (MAX-ONES(S)) and the valued constraint satisfaction problem over a set of Boolean cost functions Δ (VCSP(Δ)). For MAX-ONES(S) we use partial clone theory and prove that MAX-ONES({R}) is the easiest NP-complete MAX-ONES(S) problem. These algebraic techniques do not work for VCSP(Δ), however, where we instead use multimorphisms to prove that MAX-CUT is the easiest NP-complete Boolean VCSP(Δ) problem. Similar to the case of SAT(S) we then rule out the possibility of subexponential algorithms for these problems, unless the ETH is false.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2016. , 160 p.
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1733
National Category
Computer Science
URN: urn:nbn:se:liu:diva-122827DOI: 10.3384/diss.diva-122827ISBN: 978-91-7685-856-1 (print)OAI: diva2:874097
Public defence
2016-02-03, Alan Turing, hus E, Campus Valla, Linköpiong, 13:15 (English)
CUGS (National Graduate School in Computer Science)
Available from: 2015-12-15 Created: 2015-11-25 Last updated: 2015-12-16Bibliographically approved

Open Access in DiVA

fulltext(1104 kB)101 downloads
File information
File name FULLTEXT01.pdfFile size 1104 kBChecksum SHA-512
Type fulltextMimetype application/pdf
omslag(13424 kB)11 downloads
File information
File name COVER01.pdfFile size 13424 kBChecksum SHA-512
Type coverMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 101 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

Altmetric score

Total: 1239 hits
ReferencesLink to record
Permanent link

Direct link