New answers tagged reductions
0
votes
Are the notions of #P-completeness via Turing reductions and polynomial many-one counting reductions equivalent?
The answer to your question is in this paper Cook reductions blur structural differences between functional complexity classes.
- 2,648
1
vote
Are the notions of #P-completeness via Turing reductions and polynomial many-one counting reductions equivalent?
I believe this is open, even if you assume $\mathsf{FP} \neq \mathsf{\# P}$.
It's closely related to parsimonious reductions. If $R,S$ are relations defining languages in NP (that is, $L_R = \{x : (\...
- 38.5k
3
votes
Are the notions of #P-completeness via Turing reductions and polynomial many-one counting reductions equivalent?
Of course, if all of the functions in #P are computable in deterministic polynomial time, then the answer to your question is "no". I think that it would be a very interesting theorem if ...
- 2,356
Top 50 recent answers are included