17
$\begingroup$

The Constraint Satisfaction Problem I mentioned is similar to CNF-SAT: A variable can take values from some finite domain $D$ where $|D| = d$. A literal of variable $x$ is an expression of the form $x\neq c$, where $c\in D$. A constraint is a disjunction of literals, and a formula is a conjunction of constraints. For example, let $D=\{0,1,2\}$, then $$(x_1\neq 1\vee x_2\neq 0\vee x_3\neq 2)\wedge (x_2\neq 0\vee x_4\neq 2\vee x_5\neq 1)\wedge (x_3\neq 2\vee x_5\neq 0)$$ is a formula with $6$ variables and $3$ constraints. If we assign $x=0$, then literal $x\neq 0$ evaluates to false, and literals $x\neq 1$ and $x\neq 2$ evaluate to true. A formula is satisfiable if an assignment makes the formula evaluate to true. In CSP, the task is to decide whether the input formula is satisfiable.

CSP with $n$ variables ranging over a domain of $d$ values can be solved in $O^*(d^n)$ time (the $O^*(\cdot)$ notation omits polynomial factor) by enumerating all possible assignments. Since CSP is a generalization of CNF-SAT, I wonder if there is any hypothesis about the worst-case runtime like SETH, e.g., CSP can not be solved in $O^*(d^{(1-\epsilon)n})$ time for any constant $\epsilon>0$?

Since CNF-SAT can be reduced to CSP with $d=2$, what I want to know is the case when $d \geq 3$.

My motivation for asking this question:

  • To the best of my knowledge, I did not find a better runtime for CSP. But I did not find any SETH-like hypothesis either. I am not sure if I missed something and if "SETH for CSP" is convincing.

  • Based on SETH, one can get a conditional lower bound for a problem by reducing CNF-SAT to it. This paradigm works not only for NP-hard problems but also for problems in P. So, if there is a SETH for CSP with $d\geq 3$, maybe based on this, we can establish tighter condition lower bounds for some problems than those based on SETH for CNF-SAT?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ I assume that $d$ is constant and the number of terms in each clause is constant. 1) A variable with $d=2^k$ values can be used to encode $k$ boolean variables. For variable $x_i$ let's denote the corresponding boolean variables as $x_{i1}, \ldots, x_{ik}$. 2) You can write a condition on $x_{ij}$ by enumerating all matching values of $x_i$. E.g, if $x_{i1}$ corresponds to the lowest bit, then $x_{11} \lor \bar{x}_{22}$ can be written as $(x_1 \ne 0 \lor x_2 \ne 1) \land (x_1 \ne 2 \lor x_2 \ne 1) \land (x_1 \ne 0 \lor x_2 \ne 3) \land (x_1 \ne 2 \lor x_2 \ne 3)$. $\endgroup$
    – Dmitry
    Commented Nov 20, 2023 at 17:31
  • 1
    $\begingroup$ So, it gives a lower bound $\Omega((d/2)^{(1 - \epsilon) n})$ for arbitrary $d$. Probably you can get $\Omega(d^{(1 - \epsilon) n})$ with careful encoding. $\endgroup$
    – Dmitry
    Commented Nov 20, 2023 at 17:32
  • $\begingroup$ @Dmitry I got your idea, but a little confused with the lower bound $\Omega((d/2)^{(1-\epsilon)n})$. Following your reduction, we can reduce CNF-SAT with $n$ variables to CSP with $d=2^k$ and $n'=\frac{n}{k}=\frac{n}{\log_{2}d}$ variables. So, a $d^{({1-\epsilon}n')}$-time algorithm for CSP yields a $d^{(1-\epsilon)\frac{n}{\log_{2}d}}=2^{(1-\epsilon)n}$-time algorithm for CNF-SAT, which refutes SETH. This gives a lower bound $\Omega(d^{(1-\epsilon)n})$ for $d$ being a power of two, since in the reduction, $k$ should be an integer. Am I right? $\endgroup$
    – Junqiang Peng
    Commented Nov 21, 2023 at 4:08
  • 2
    $\begingroup$ From the title I expected this question to be about general CSPs, but I see the question is only about one specific example of a CSP. Knowing that some CSPs are PTIME and some are NP-hard (and this is now known to be a dichotomy), one could wonder which of the hard CSPs are "equivalent" to SETH, i.e., assuming they are not solvable in subexponential time is equivalent to SETH? But there seems to be work in that direction already epubs.siam.org/doi/abs/10.1137/1.9781611973105.92 $\endgroup$
    – Antoine Amarilli 'a3nm'
    Commented Nov 24, 2023 at 18:15
  • 2
    $\begingroup$ FWIW, the CSP the OP asks about is "CSP-complete" via a fine-grained (arity- and #-of-variables-preserving) reduction, so the question is equivalent to asking about general CSPs. The idea is to map each general CSP constraint $C : [d]^k \to \{0, 1\}$ to $|C^{-1}(0)|$ many "OP CSP" (a.k.a $(d, k)$-SAT) constraints, each disallowing one of the assignments in $C^{-1}(0)$. $\endgroup$
    – Huck Bennett
    Commented Nov 24, 2023 at 23:16

2 Answers 2

Reset to default
15
$\begingroup$

This CSP is known to be SETH-hard. More precisely, assuming SETH, for any constant $\varepsilon > 0$ there is no $d^{(1-\varepsilon)n}$-time algorithm for solving this CSP with domain size $d$.

This is proved in Theorem 3.3 in https://eccc.weizmann.ac.il/report/2019/159/. Note that their $q$ is your $d$, and that they describe their $(q,k)$-SAT constraints in a different but equivalent way (in both cases they're functions $[q]^k \to \{0,1\}$ such that the preimage of $0$ has size exactly $1$, i.e., there's exactly one way to falsify each constraint).

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Thank you, this is the best possible answer that I was hoping for. I'm a little surprised there wasn't such a statement until 2019. In the paper you referenced, it says: "In a different context, Traxler proved a slightly weaker result, which in our terminology corresponds to a lower bound of $2^{(1−\epsilon)n\lceil \log_{2}q\rceil}$. This is weaker, e.g., for constant $q$ that is not a power of two." $\endgroup$
    – Junqiang Peng
    Commented Nov 21, 2023 at 4:30
  • $\begingroup$ I also noticed that in Section 3 of the paper you mentioned, it says "we will always take $q$ to be a prime power". I am not familiar with abstract algebra. So just to double-check, does the SETH-hardness proved in the paper hold for any constant $q$, or just for $q$ being a prime power? Thank you. $\endgroup$
    – Junqiang Peng
    Commented Nov 21, 2023 at 5:09
  • $\begingroup$ There is a typo in the previous comment, the lower bound proved by Traxler should be $2^{(1-\epsilon)n\lfloor \log_{2}{q}\rfloor}$ (round-down instead of round-up). $\endgroup$
    – Junqiang Peng
    Commented Nov 21, 2023 at 9:36
  • 2
    $\begingroup$ The result holds for all integer $q \geq 2$, but the authors (only) use the case where $q$ is a prime power for their hardness results about coding problems. $\endgroup$
    – Huck Bennett
    Commented Nov 21, 2023 at 16:19
  • $\begingroup$ Got it. Thanks for your explanation! $\endgroup$
    – Junqiang Peng
    Commented Nov 21, 2023 at 16:41
8
$\begingroup$

To give an alternative (slightly older) reference to the one proposed in another answer, the result "If the SETH is true, then $n$-variable CSP over alphabets of size $d$ cannot be solved in time $(d-\varepsilon)^n$" is given for all fixed $d\ge 3$ in my paper "Finer Tight Bounds for Coloring on Clique-width" (https://arxiv.org/abs/1804.07975).

To be fair, and despite the self-promotion, I'm not actually claiming that I deserve credit for this result. The technique of mapping groups of binary variables of the original SAT instance into groups of $d$-ary variables of the new instance, in a way that we don't mind that $\log d$ is not an integer, goes back to Lokshtanov, Marx, and Saurabh (https://arxiv.org/abs/1007.5450), who used this to show that Dominating Set cannot be solved in time $(3-\varepsilon)^{tw}n^{O(1)}$. The same technique has also been used in several follow-up papers that show lower bounds of the form $c^kn^{O(1)}$, where $c$ is not a power of $2$. My paper only puts what they already did in a packaged lemma that is easy to reuse. I guess this also implicitly addresses the comment that "This should have been known before 2019", since this paper is from 2010.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yes, your answer has really cleared up my doubts. Before now, my guess was that this result may have been given implicitly in some earlier paper (instead of 2019) that proves SETH-hardness for some specific problem. Thank you for providing these references. They are helpful to me. I gave you a vote since I have accepted the previous answer. $\endgroup$
    – Junqiang Peng
    Commented Nov 22, 2023 at 3:18
  • 1
    $\begingroup$ Hi Michael, cool, and sorry not to have known about your work (+1)! I read your Thm. 2 proof, and I think there's a small difference between it and the result I mentioned: you reduce $q$-SAT to $(qp)$-CSP-$B$ where arbitrary CSP constraints are allowed, and not just ones of the type mentioned by the OP. (In your reduction, an output $(qp)$-constraint has exactly one falsifying assignment iff the map from assignments to $V_{i_1} \cup \cdots \cup V_{i_q}$ to $X_{i_1} \cup \cdots \cup X_{i_q}$ is bijective and not just injective.) You can in turn reduce this to "$(qp)$-SAT-$B$" though. $\endgroup$
    – Huck Bennett
    Commented Nov 24, 2023 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.