Questions tagged [exact-counting]
The exact-counting tag has no summary.
3 questions
0
votes
0
answers
141
views
Complexity class of $\#\mathrm{P}$-hard counting problem can be reduced to $\#\mathrm{P}$ given its own output for different values
I have a counting problem that famously has evaded being solved by simply counting the elements of a set and somehow seemed to have involved subtraction in an essential way (it is in $\mathrm{GapP}^+$,...
- 133
1
vote
1
answer
122
views
Complexity class of a specific counting problem
I have a counting problem that I know is in $\mathrm{GapP}^+$, and if it is in $\#P$ it subsumes another $\#P$-complete problem entirely. I found a solution to the problem that involves identifying ...
- 133
1
vote
0
answers
49
views
Help me understand Valiant's $\#P_1$-completeness reduction
In his paper on the complexity of counting problems, Valiant presents a reduction from a counting nondeterministic Turing machine to a problem he calls $A$-SUBSET-PATTERNS. In this problem, we are ...
- 11