<p>Without further assumption the bound on the number of solutions you give isn't going to help. The reason is that there is an easy transformation of an arbitrary CSP problem into one that either continues to have no solutions (if the original problem had no solutions) or that has an exponential number of solutions (if the original problem has at least one solution): just add a linear number of irrelevant and unconstrained variables. So if you could find a solution quickly when there are an exponential number, you could apply this method to the output of this transformation and use it to find a solution quickly even when there is only one.</p>

CC BY-SA 3.0
2013-02-02T02:09:15.277Z
What further assumptions would help? Are there any particular examples for particular classes of CSPs?
Turbo
CC BY-SA 3.0
2013-02-02T02:15:01.473Z
"Are there any particular examples for particular classes of CSPs where an exp # of solutions would help?"
Turbo
CC BY-SA 3.0
2013-02-02T20:02:38.403Z
I'm skeptical that there are natural and well studied classes of CSPs that are not polynomially solvable in general but that are polynomially solvable when there is an exponential number of satisfying solutions that is still small enough that it forms an exponentially tiny fraction of all potential solutions (what you seem to be asking for). My answer explains why: it is too easy to transform a solvable/unsolvable dichotomy to exponential solutions/no solutions. So any such class would have to somehow rule out this kind of transformation.
David Eppstein
CC BY-SA 3.0
2013-02-02T02:02:17.757Z
2013-02-02T02:02:17.757Z
David Eppstein
<p>Say we have a constraint satisfaction problem parametrized by $n$ number of variables whose solution lies in a set of bounded non-negative integers of size $O(2^{n})$. Say we also know that we have $O(2^{an})$ satisfying solutions for the $n$ number of variables for some $a \in (0,1)$. Are there any known cases where such problems can be solved in polynomial in $n$ time?</p>

CC BY-SA 3.0
2013-02-02T10:23:20.583Z
Perhaps (but it is only a vague idea), when there is some kind of "automorphism" in the structure of the CSP problem.
Marzio De Biasi
<cc.complexity-theory>
Constaint Satisfaction problem with exponentially many solutions
Turbo
# Constaint Satisfaction problem with exponentially many solutions

(Asked by: username_0 on 2013-02-02)

Say we have a constraint satisfaction problem parametrized by $n$ number of variables whose solution lies in a set of bounded non-negative integers of size $O(2^{n})$. Say we also know that we have $O(2^{an})$ satisfying solutions for the $n$ number of variables for some $a \in (0,1)$. Are there any known cases where such problems can be solved in polynomial in $n$ time?

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: Perhaps (but it is only a vague idea), when there is some kind of "automorphism" in the structure of the CSP problem.  

---

## 1 answers

### Answer by username_2 on 2013-02-02. Score: 11 | Accepted answer

Without further assumption the bound on the number of solutions you give isn't going to help. The reason is that there is an easy transformation of an arbitrary CSP problem into one that either continues to have no solutions (if the original problem had no solutions) or that has an exponential number of solutions (if the original problem has at least one solution): just add a linear number of irrelevant and unconstrained variables. So if you could find a solution quickly when there are an exponential number, you could apply this method to the output of this transformation and use it to find a solution quickly even when there is only one.

> **Comments:**
> **username_0**: What further assumptions would help? Are there any particular examples for particular classes of CSPs?  
> **username_0**: "Are there any particular examples for particular classes of CSPs where an exp # of solutions would help?"  
> **username_2**: I'm skeptical that there are natural and well studied classes of CSPs that are not polynomially solvable in general but that are polynomially solvable when there is an exponential number of satisfying solutions that is still small enough that it forms an exponentially tiny fraction of all potential solutions (what you seem to be asking for). My answer explains why: it is too easy to transform a solvable/unsolvable dichotomy to exponential solutions/no solutions. So any such class would have to somehow rule out this kind of transformation.  

---

