Questions tagged [exact-counting]
The exact-counting tag has no summary.
2 questions with no upvoted or accepted answers
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
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