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?
Tell me more
×
Theoretical Computer Science Stack Exchange is a question and answer site for
theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
|
|
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. |
|||||||||||
|
