<p>To give an alternative (slightly older) reference to the one proposed in another answer, the result &quot;If the SETH is true, then <span class="math-container">$n$</span>-variable CSP over alphabets of size <span class="math-container">$d$</span> cannot be solved in time <span class="math-container">$(d-\varepsilon)^n$</span>&quot; is given for all fixed <span class="math-container">$d\ge 3$</span> in my paper &quot;Finer Tight Bounds for Coloring on Clique-width&quot; (<a href="https://arxiv.org/abs/1804.07975" rel="noreferrer">https://arxiv.org/abs/1804.07975</a>).</p>
<p>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 <span class="math-container">$d$</span>-ary variables of the new instance, in a way that we don't mind that <span class="math-container">$\log d$</span> is not an integer, goes back to Lokshtanov, Marx, and Saurabh (<a href="https://arxiv.org/abs/1007.5450" rel="noreferrer">https://arxiv.org/abs/1007.5450</a>), who used this to show that Dominating Set cannot be solved in time <span class="math-container">$(3-\varepsilon)^{tw}n^{O(1)}$</span>. The same technique has also been used in several follow-up papers that show lower bounds of the form <span class="math-container">$c^kn^{O(1)}$</span>, where <span class="math-container">$c$</span> is not a power of <span class="math-container">$2$</span>. 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 &quot;This should have been known before 2019&quot;, since this paper is from 2010.</p>

CC BY-SA 4.0
2023-11-22T03:18:12.047Z
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.
Junqiang Peng
CC BY-SA 4.0
2023-11-24T22:06:09.937Z
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.
Huck Bennett
CC BY-SA 4.0
2023-11-21T21:18:11.710Z
2023-11-21T21:18:11.710Z
Michael Lampis
<p>This CSP is known to be SETH-hard. More precisely, assuming SETH, for any constant <span class="math-container">$\varepsilon &gt; 0$</span> there is no <span class="math-container">$d^{(1-\varepsilon)n}$</span>-time algorithm for solving this CSP with domain size <span class="math-container">$d$</span>.</p>
<p>This is proved in Theorem 3.3 in <a href="https://eccc.weizmann.ac.il/report/2019/159/" rel="noreferrer">https://eccc.weizmann.ac.il/report/2019/159/</a>. Note that their <span class="math-container">$q$</span> is your <span class="math-container">$d$</span>, and that they describe their <span class="math-container">$(q,k)$</span>-SAT constraints in a different but equivalent way (in both cases they're functions <span class="math-container">$[q]^k \to \{0,1\}$</span> such that the preimage of <span class="math-container">$0$</span> has size exactly <span class="math-container">$1$</span>, i.e., there's exactly one way to falsify each constraint).</p>

CC BY-SA 4.0
2023-11-21T04:30:31.660Z
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](https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=27dd54d50893f91c16fa3a6ab3fafa106234fd47), 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."
Junqiang Peng
CC BY-SA 4.0
2023-11-21T05:09:02.777Z
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.
Junqiang Peng
CC BY-SA 4.0
2023-11-21T09:36:21.317Z
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).
Junqiang Peng
CC BY-SA 4.0
2023-11-21T16:19:18.633Z
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.
Huck Bennett
CC BY-SA 4.0
2023-11-21T16:41:02.817Z
Got it. Thanks for your explanation!
Junqiang Peng
CC BY-SA 4.0
2023-11-20T19:03:25.867Z
2023-11-20T19:03:25.867Z
Huck Bennett
<p>The Constraint Satisfaction Problem I mentioned is similar to CNF-SAT: A variable can take values from some finite domain <span class="math-container">$D$</span> where <span class="math-container">$|D| = d$</span>. A literal of variable <span class="math-container">$x$</span> is an expression of the form <span class="math-container">$x\neq c$</span>, where <span class="math-container">$c\in D$</span>. A constraint is a disjunction of literals, and a formula is a conjunction of constraints.
For example, let <span class="math-container">$D=\{0,1,2\}$</span>, then
<span class="math-container">$$(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)$$</span>
is a formula with <span class="math-container">$6$</span> variables and <span class="math-container">$3$</span> constraints.
If we assign <span class="math-container">$x=0$</span>, then literal <span class="math-container">$x\neq 0$</span> evaluates to false, and literals <span class="math-container">$x\neq 1$</span> and <span class="math-container">$x\neq 2$</span> 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.</p>
<p>CSP with <span class="math-container">$n$</span> variables ranging over a domain of <span class="math-container">$d$</span> values can be solved in <span class="math-container">$O^*(d^n)$</span> time (the <span class="math-container">$O^*(\cdot)$</span> 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 <span class="math-container">$O^*(d^{(1-\epsilon)n})$</span> time for any constant <span class="math-container">$\epsilon&gt;0$</span>?</p>
<p>Since CNF-SAT can be reduced to CSP with <span class="math-container">$d=2$</span>, what I want to know is the case when <span class="math-container">$d \geq 3$</span>.</p>
<p><strong>My motivation for asking this question</strong>:</p>
<ul>
<li><p>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 &quot;SETH for CSP&quot; is convincing.</p>
</li>
<li><p>Based on SETH, one can get a conditional lower bound for a problem by reducing CNF-SAT to it. This paradigm works not only <a href="https://arxiv.org/abs/1112.2275" rel="noreferrer">for NP-hard problems</a> but also <a href="https://people.csail.mit.edu/virgi/eccentri.pdf" rel="noreferrer">for problems in P</a>.
So, if there is a SETH for CSP with <span class="math-container">$d\geq 3$</span>, maybe based on this, we can establish tighter condition lower bounds for some problems than those based on SETH for CNF-SAT?</p>
</li>
</ul>

CC BY-SA 4.0
2023-11-20T17:31:38.827Z
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)$.
Dmitry
CC BY-SA 4.0
2023-11-20T17:32:54.527Z
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.
Dmitry
CC BY-SA 4.0
2023-11-21T04:08:54.040Z
@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?
Junqiang Peng
CC BY-SA 4.0
2023-11-21T05:49:55.477Z
It gives $\Omega(d^{(1 - \epsilon) n})$ when $d$ is the power of two. For arbitrary $d$, there is always a power of two $2^k$ between $d/2$ and $d$, which gives lower bound $\Omega((2^k)^{(1 - \epsilon) n}) = \Omega((d/2)^{(1 - \epsilon) n})$.
Dmitry
CC BY-SA 4.0
2023-11-21T06:52:10.660Z
Oh, it's clear to me now. Nice reduction. Thank you!
Junqiang Peng
CC BY-SA 4.0
2023-11-24T18:15:21.357Z
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 https://epubs.siam.org/doi/abs/10.1137/1.9781611973105.92
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-11-24T23:16:20.803Z
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)$.
Huck Bennett
<reference-request><time-complexity><sat><lower-bounds><csp>
Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?
Junqiang Peng
# Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?

(Asked by: username_0 on 2023-11-20)

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](https://arxiv.org/abs/1112.2275) but also [for problems in P](https://people.csail.mit.edu/virgi/eccentri.pdf).
  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?

**Tags:** reference-request, time-complexity, sat, lower-bounds, csp
> **Comments:**
> **username_1**: 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)$.  
> **username_1**: 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.  
> **username_0**: @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?  
> **username_1**: It gives $\Omega(d^{(1 - \epsilon) n})$ when $d$ is the power of two. For arbitrary $d$, there is always a power of two $2^k$ between $d/2$ and $d$, which gives lower bound $\Omega((2^k)^{(1 - \epsilon) n}) = \Omega((d/2)^{(1 - \epsilon) n})$.  
> **username_0**: Oh, it's clear to me now. Nice reduction. Thank you!  
> **username_2**: 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 https://epubs.siam.org/doi/abs/10.1137/1.9781611973105.92  
> **username_3**: 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)$.  

---

## 2 answers

### Answer by username_3 on 2023-11-20. Score: 15 | Accepted answer

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).

> **Comments:**
> **username_0**: 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](https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=27dd54d50893f91c16fa3a6ab3fafa106234fd47), 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."  
> **username_0**: 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.  
> **username_0**: 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).  
> **username_3**: 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.  
> **username_0**: Got it. Thanks for your explanation!  

---

### Answer by username_4 on 2023-11-21. Score: 8

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.

> **Comments:**
> **username_0**: 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.  
> **username_3**: 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.  

---

