liu.seSearch for publications in DiVA
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
Applications of Partial Polymorphisms in (Fine-Grained) Complexity of Constraint Satisfaction Problems
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
2020 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

In this thesis we study the worst-case complexity ofconstraint satisfaction problems and some of its variants. We use methods from universal algebra: in particular, algebras of total functions and partial functions that are respectively known as clones and strong partial clones. The constraint satisfactionproblem parameterized by a set of relations Γ (CSP(Γ)) is the following problem: given a set of variables restricted by a set of constraints based on the relations Γ, is there an assignment to thevariables that satisfies all constraints? We refer to the set Γ as aconstraint language. The inverse CSPproblem over Γ (Inv-CSP(Γ)) asks the opposite: given a relation R, does there exist a CSP(Γ) instance with R as its set of models? When Γ is a Boolean language, then we use the term SAT(Γ) instead of CSP(Γ) and Inv-SAT(Γ) instead of Inv-CSP(Γ).

Fine-grained complexity is an approach in which we zoom inside a complexity class and classify theproblems in it based on their worst-case time complexities. We start by investigating the fine-grained complexity of NP-complete CSP(Γ) problems. An NP-complete CSP(Γ) problem is said to be easier than an NP-complete CSP(∆) problem if the worst-case time complexity of CSP(Γ) is not higher thanthe worst-case time complexity of CSP(∆). We first analyze the NP-complete SAT problems that are easier than monotone 1-in-3-SAT (which can be represented by SAT(R) for a certain relation R), and find out that there exists a continuum of such problems. For this, we use the connection between constraint languages and strong partial clones and exploit the fact that CSP(Γ) is easier than CSP(∆) when the strong partial clone corresponding to  Γ contains the strong partial clone of ∆. An NP-complete CSP(Γ) problem is said to be the easiest with respect to a variable domain D if it is easier than any other NP-complete CSP(∆) problem of that domain. We show that for every finite domain there exists an easiest NP-complete problem for the ultraconservative CSP(Γ) problems. An ultraconservative CSP(Γ) is a special class of CSP problems where the constraint language containsall unary relations. We additionally show that no NP-complete CSP(Γ) problem can be solved insub-exponential time (i.e. in2^o(n) time where n is the number of variables) given that theexponentialtime hypothesisis true.

Moving to classical complexity, we show that for any Boolean constraint language Γ, Inv-SAT(Γ) is either in P or it is coNP-complete. This is a generalization of an earlier dichotomy result, which was only known to be true for ultraconservative constraint languages. We show that Inv-SAT(Γ) is coNP-complete if and only if the clone corresponding to Γ contains essentially unary functions only. For arbitrary finite domains our results are not conclusive, but we manage to prove that theinversek-coloring problem is coNP-complete for each k>2. We exploit weak bases to prove many of theseresults. A weak base of a clone C is a constraint language that corresponds to the largest strong partia clone that contains C. It is known that for many decision problems X(Γ) that are parameterized bya constraint language Γ(such as Inv-SAT), there are strong connections between the complexity of X(Γ) and weak bases. This fact can be exploited to achieve general complexity results. The Boolean domain is well-suited for this approach since we have a fairly good understanding of Boolean weak bases. In the final result of this thesis, we investigate the relationships between the weak bases in the Boolean domain based on their strong partial clones and completely classify them according to the setinclusion. To avoid a tedious case analysis, we introduce a technique that allows us to discard a largenumber of cases from further investigation.

Place, publisher, year, edition, pages
Linköping:: Linköping University Electronic Press, 2020. , p. 30
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 2048
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-164157DOI: 10.3384/diss.diva-164157ISBN: 9789179298982 (print)OAI: oai:DiVA.org:liu-164157DiVA, id: diva2:1412762
Public defence
2020-04-23, Ada Lovelace, B-Building, Campus Valla, Linköping, 13:15 (English)
Opponent
Supervisors
Funder
CUGS (National Graduate School in Computer Science)Available from: 2020-03-23 Created: 2020-03-07 Last updated: 2020-03-31Bibliographically approved
List of papers
1. A Preliminary Investigation of Satisfiability Problems NotHarder than 1-in-3-SAT
Open this publication in new window or tab >>A Preliminary Investigation of Satisfiability Problems NotHarder than 1-in-3-SAT
2016 (English)Conference paper, Published paper (Refereed)
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-164152 (URN)
Conference
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS-2016)
Available from: 2020-03-07 Created: 2020-03-07 Last updated: 2020-03-07
2. On the Interval of Boolean Strong Partial ClonesContaining Only Projections as Total Operations
Open this publication in new window or tab >>On the Interval of Boolean Strong Partial ClonesContaining Only Projections as Total Operations
2017 (English)Conference paper, Published paper (Refereed)
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-164153 (URN)
Conference
47th International Symposium on Multiple-Valued Logic (ISMVL-2017)
Available from: 2020-03-07 Created: 2020-03-07 Last updated: 2020-03-07
3. Time Complexity of Constraint Satisfaction via Universal Algebra
Open this publication in new window or tab >>Time Complexity of Constraint Satisfaction via Universal Algebra
2017 (English)Conference paper, Published paper (Refereed)
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-164154 (URN)
Conference
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS-2017)
Available from: 2020-03-07 Created: 2020-03-07 Last updated: 2020-03-07
4. A Dichotomy Theorem for the Inverse Satisfiability Problem
Open this publication in new window or tab >>A Dichotomy Theorem for the Inverse Satisfiability Problem
2018 (English)Conference paper, Published paper (Refereed)
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-164155 (URN)
Conference
37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS-2017)
Available from: 2020-03-07 Created: 2020-03-07 Last updated: 2020-03-07
5. The Inclusion Structure of Boolean Weak Bases
Open this publication in new window or tab >>The Inclusion Structure of Boolean Weak Bases
2019 (English)In: 2019 IEEE 49TH INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC (ISMVL), IEEE , 2019, p. 31-36Conference paper, Published paper (Refereed)
Abstract [en]

Strong partial clones are composition closed sets of partial operations containing all partial projections, characterizable as partial polymorphisms of sets of relations Gamma (pPol(Gamma)). If C is a clone it is known that the set of all strong partial clones whose total component equals C, has a greatest element pPol(Gamma(w)), where Gamma(w) is called a weak base. Weak bases have seen applications in computer science due to their usefulness for proving complexity classifications for constraint satisfaction related problems. In this paper we completely describe the inclusion structure between pPol(Gamma(w)), pPol(Delta(w)) for all Boolean weak bases Gamma(w), and Delta(w.)

Place, publisher, year, edition, pages
IEEE, 2019
Series
International Symposium on Multiple-Valued Logic, ISSN 0195-623X
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-160634 (URN)10.1109/ISMVL.2019.00014 (DOI)000484992100006 ()978-1-7281-0092-0 (ISBN)
Conference
49th IEEE International Symposium on Multiple-Valued Logic (ISMVL)
Available from: 2019-10-11 Created: 2019-10-11 Last updated: 2020-03-07

Open Access in DiVA

fulltext(5025 kB)75 downloads
File information
File name FULLTEXT02.pdfFile size 5025 kBChecksum SHA-512
61471f010042619d3867fd4aa46cad93a0b89a12c11f45be14dd580117ae748541249b1389eb4408494de5de11cba5b15e0e441bc2488db31a957e99d285a0b0
Type fulltextMimetype application/pdf
Order online >>

Other links

Publisher's full text

Authority records BETA

Roy, Biman

Search in DiVA

By author/editor
Roy, Biman
By organisation
Software and SystemsFaculty of Science & Engineering
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 75 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
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 748 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