All Questions
Tagged with unique-solution counting-complexity
2 questions
7
votes
0
answers
185
views
Variation of (derandomized) Valiant-Vazirani
I am interested in the following "improvement" of the Valiant-Vazirani reduction. As pointed out here, under the right derandomization assumptions one can obtain a deterministic polynomial-...
- 1,049
7
votes
1
answer
649
views
What's the relationship between ASP-complete and #P-complete?
Given that ASP-reductions by definition are parsimonious and parsimonious reductions preserve #P-completeness, one might think that the counting version of all ASP-complete problems are also #P-...
- 249