| 1. |
|
|
| 2. |
|
|
| 3. |
- Jonsson, Peter, et al.
(författare)
-
Fine-Grained Time Complexity of Constraint Satisfaction Problems
- 2021
-
Ingår i: ACM Transactions on Computation Theory. - : ASSOC COMPUTING MACHINERY. - 1942-3454 .- 1942-3462. ; 13:1
-
Tidskriftsartikel (refereegranskat)abstract
- We study the constraint satisfaction problem (CSP) parameterized by a constraint language F (CSP(F)) and how the choice of F affects its worst-case time complexity. Under the exponential-time hypothesis (ETH), we rule out the existence of subexponential algorithms for finite-domain NP-complete CSP(F) problems. This extends to certain infinite-domain CSPs and structurally restricted problems. For CSPs with finite domain D and where all unary relations are available, we identify a relation S-D such that the time complexity of the NP-complete problem CSP({S-D}) is a lower bound for all NP-complete CSPs of this kind. We also prove that the time complexity of CSP({S-D}) strictly decreases when vertical bar D vertical bar increases (unless the ETH is false) and provide stronger complexity results in the special case when vertical bar D vertical bar = 3.
|
|
| 4. |
- Jonsson, Peter, 1969-, et al.
(författare)
-
Time Complexity of Constraint Satisfaction via Universal Algebra
- 2017
-
Konferensbidrag (refereegranskat)abstract
- The exponential-time hypothesis (ETH) states that 3-SAT is not solvable in subexponential time,i.e. not solvable in O(cn) time for arbitrary c > 1, where n denotes the number of variables.Problems like k-SAT can be viewed as special cases of the constraint satisfaction problem (CSP),which is the problem of determining whether a set of constraints is satisfiable. In this paperwe study the worst-case time complexity of NP-complete CSPs. Our main interest is in theCSP problem parameterized by a constraint language Γ (CSP(Γ)), and how the choice of Γaffects the time complexity. It is believed that CSP(Γ) is either tractable or NP-complete, andthe algebraic CSP dichotomy conjecture gives a sharp delineation of these two classes based onalgebraic properties of constraint languages. Under this conjecture and the ETH, we first rule outthe existence of subexponential algorithms for finite-domain NP-complete CSP(Γ) problems. Thisresult also extends to certain infinite-domain CSPs and structurally restricted CSP(Γ) problems.We then begin a study of the complexity of NP-complete CSPs where one is allowed to arbitrarilyrestrict the values of individual variables, which is a very well-studied subclass of CSPs. For suchCSPs with finite domain D, we identify a relation SD such that (1) CSP({SD}) is NP-completeand (2) if CSP(Γ) over D is NP-complete and solvable in O(cn) time, then CSP({SD}) is solvablein O(cn) time, too. Hence, the time complexity of CSP({SD}) is a lower bound for all CSPs ofthis particular kind. We also prove that the complexity of CSP({SD}) is decreasing when |D|increases, unless the ETH is false. This implies, for instance, that for every c > 1 there exists afinite-domain Γ such that CSP(Γ) is NP-complete and solvable in O(cn) time
|
|
| 5. |
|
|
| 6. |
|
|
| 7. |
|
|
| 8. |
- Lagerkvist, Victor, 1987-, et al.
(författare)
-
C-Maximal Strong Partial Clones and the Inclusion Structure of Boolean Weak Bases
- 2022
-
Ingår i: Journal of Multiple-Valued Logic and Soft Computing. - Philadelphia, PA, United States : Old City Publishing. - 1542-3980 .- 1542-3999. ; 38:3-4, s. 333-353
-
Tidskriftsartikel (refereegranskat)abstract
- Strong partial clones are composition closed sets of partial operations containing all partial projections, characterizable as partial polymorphisms of sets of relations Γ (pPol(Γ)). 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(Γω), where Γω 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 article we (1) completely describe the inclusion structure between pPol(Γω), pPol(Δω) for all Boolean weak bases Γω and Δω and (2) in many such cases prove that the strong partial clones in question uniquely cover each other.
|
|
| 9. |
- Lagerkvist, Victor, 1987-, et al.
(författare)
-
Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem
- 2021
-
Ingår i: Journal of computer and system sciences (Print). - : Elsevier. - 0022-0000 .- 1090-2724. ; 117, s. 23-39
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 10. |
|
|
| 11. |
- Lagerkvist, Victor, 1987-, et al.
(författare)
-
The Inclusion Structure of Boolean Weak Bases
- 2019
-
Ingår i: 2019 IEEE 49TH INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC (ISMVL). - : IEEE. - 9781728100920 ; , s. 31-36
-
Konferensbidrag (refereegranskat)abstract
- 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.)
|
|
| 12. |
- Roy, Biman, 1989-
(författare)
-
Applications of Partial Polymorphisms in (Fine-Grained) Complexity of Constraint Satisfaction Problems
- 2020
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
