<p>Commonly occurring #P problems (e.g., #SAT) are often studied in the regime where instances with <span class="math-container">$n$</span> Boolean variables have <span class="math-container">$2^{\Theta(n)}$</span> solutions, in part because instances with <span class="math-container">$O(1)$</span> solutions can be naively solved by repeated application of a NP solver.</p>
<p>Are there any interesting / natural / commonly occurring counting problems with polynomially many solutions that remain hard?</p>

CC BY-SA 4.0
2024-12-09T21:25:14.997Z
I'm confused, in particular by the last paragraph. When there are at most poly(n) solutions one can still count them deterministically with an NP oracle in O(log n) queries. To check if there are at least k solutions, the new witness is simply a concatenation of k distinct witnesses. This is an NP call when k is at most poly(n). So we can binary search in O(log n) queries.
Ryan Williams
CC BY-SA 4.0
2024-12-09T22:08:16.820Z
I see the point that the cost of the queries stays exponential. In practice, though, the size of the largest instance to be solved in the binary search would be multiplied by a poly(n) factor, which would translate to a huge overhead in the oracle runtime. You're just hiding that in the oracle call. Perhaps the question can be phrased better to take all this into account, in which case feel free to edit / suggest edits.
delete000
CC BY-SA 4.0
2024-12-09T22:18:28.363Z
I don't know about "natural", but the relevant complexity class is called [FewP](https://complexityzoo.net/Complexity_Zoo:F#fewp).
Joshua Grochow
CC BY-SA 4.0
2024-12-10T05:42:21.223Z
If there are only polynomially many solutions, then a sufficiently precise approximate counting is actually exact.
Emil Jeřábek
CC BY-SA 4.0
2024-12-11T10:36:29.757Z
@EmilJeřábek could you explain this? Can the precision be increased sufficiently without incurring an extra n-dependent cost?
delete000
CC BY-SA 4.0
2024-12-11T10:44:34.810Z
A hashing-based approximate counting can count the result with relative error $1/p(n)$ for any polynomial $p$. If the number of solutions is polynomially bounded in $n$, you can choose $p(n)$ to be more than twice the bound on the number of solutions, in which case an approximation with such relative error will be exact (assuming it is rounded to the nearest integer, in case it isn’t already). (But I do not see much point in this. Asking the oracle to find hash collisions is surely not more efficient than asking it to directly count the solutions as in Ryan Williams’s comment.)
Emil Jeřábek
<cc.complexity-theory><approximation-algorithms><sat><counting-complexity><hash-function>
Interesting counting problems with polynomially many solutions
delete000
# Interesting counting problems with polynomially many solutions

(Asked by: username_0 on 2024-12-09)

Commonly occurring #P problems (e.g., #SAT) are often studied in the regime where instances with $n$ Boolean variables have $2^{\Theta(n)}$ solutions, in part because instances with $O(1)$ solutions can be naively solved by repeated application of a NP solver.

Are there any interesting / natural / commonly occurring counting problems with polynomially many solutions that remain hard?

**Tags:** cc.complexity-theory, approximation-algorithms, sat, counting-complexity, hash-function
> **Comments:**
> **username_1**: I'm confused, in particular by the last paragraph. When there are at most poly(n) solutions one can still count them deterministically with an NP oracle in O(log n) queries. To check if there are at least k solutions, the new witness is simply a concatenation of k distinct witnesses. This is an NP call when k is at most poly(n). So we can binary search in O(log n) queries.  
> **username_0**: I see the point that the cost of the queries stays exponential. In practice, though, the size of the largest instance to be solved in the binary search would be multiplied by a poly(n) factor, which would translate to a huge overhead in the oracle runtime. You're just hiding that in the oracle call. Perhaps the question can be phrased better to take all this into account, in which case feel free to edit / suggest edits.  
> **username_2**: I don't know about "natural", but the relevant complexity class is called [FewP](https://complexityzoo.net/Complexity_Zoo:F#fewp).  
> **username_3**: If there are only polynomially many solutions, then a sufficiently precise approximate counting is actually exact.  
> **username_0**: @EmilJeřábek could you explain this? Can the precision be increased sufficiently without incurring an extra n-dependent cost?  
> **username_3**: A hashing-based approximate counting can count the result with relative error $1/p(n)$ for any polynomial $p$. If the number of solutions is polynomially bounded in $n$, you can choose $p(n)$ to be more than twice the bound on the number of solutions, in which case an approximation with such relative error will be exact (assuming it is rounded to the nearest integer, in case it isn’t already). (But I do not see much point in this. Asking the oracle to find hash collisions is surely not more efficient than asking it to directly count the solutions as in Ryan Williams’s comment.)  

---

## 0 answers

