Change search
ReferencesLink to record
Permanent link

Direct link
Restricted Constraint Satisfaction Problems and the Exponential-time Hypothesis
Linköping University, Department of Computer and Information Science. Linköping University, The Institute of Technology. (TCSLAB - Theoretical Computer Science Laboratory)
2012 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

A constraint satisfaction problem (CSP) can be represented as two structures: the structure induced by the variables and the structure induced by the constraint language. Both these parameters are amenable to restrictions which affects the complexity of the resulting problems. In this thesis we shall use both constraint language restrictions and structural restrictions in order to create problems that can be solved as efficiently as possible. The language restrictions are based on creating a language that in terms of frozen partial clone theory has the largest number of polymorphic functions. Such a language can according to the Galois connection between functions and relations be implemented by as many languages as possible and is therefore the Boolean language with the lowest complexity. The structural restrictions are mainly based on limiting the number of times a variable is allowed to occur in an instance. We shall prove that the easiest language does not contain a Delta-matroid relation and is NP-complete even with the very restricted structure where no variable can occur in more than two constraints. We also give a branch-and-reduce algorithm for this problem with time complexity O(1.0493^n). This problem is then related to the exponential-time hypothesis, which postulates that k-SAT is not sub-exponential for k >= 3. We show that the exponential-time hypothesis holds if and only if this restricted problem is not sub-exponential, if and only if all NP-complete Boolean languages are not sub-exponential. In the process we also prove a stronger version of Impagliazzo's sparsification lemma for k-SAT; namely that all finite, NP-complete Boolean languages can be sparsified into each other. This should be contrasted with Santhanam's negative result which states that the same does not hold for all infinite Boolean languages.

Place, publisher, year, edition, pages
2012. , 60 p.
Keyword [en]
Constraint satisfaction, computational complexity, clone theory
National Category
Computer Science
URN: urn:nbn:se:liu:diva-82343ISRN: LIU-IDA/LITH-EX-A--12/035--SEOAI: diva2:558073
Subject / course
Master's programme in Computer Science
Von Neumann, Linköping (Swedish)
Available from: 2012-10-02 Created: 2012-10-01 Last updated: 2012-10-02Bibliographically approved

Open Access in DiVA

thesis(680 kB)357 downloads
File information
File name FULLTEXT01.pdfFile size 680 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Lagerkvist, Victor
By organisation
Department of Computer and Information ScienceThe Institute of Technology
Computer Science

Search outside of DiVA

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

Total: 233 hits
ReferencesLink to record
Permanent link

Direct link