Return to Question

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 there is an assignment that 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?

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?

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 $F=(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 there is an assignment that 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?

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 there is an assignment that 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?