# Constaint Satisfaction problem with exponentially many solutions

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?

• 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 Feb 2 '13 at 10:23