<p>Of course, if all of the functions in #P are computable in deterministic polynomial time, then the answer to your question is &quot;no&quot;.  I think that it would be a very interesting theorem if one could prove unconditionally that the answer is &quot;no&quot;.  I am rather confident that the answer to your question is not known.</p>
<p>Note that there are very likely many functions in <span class="math-container">$FP^{\#P}$</span> that are not in #P.  There is a recent paper by Ikenmeyer &amp; Pak (FOCS 2022) discussing various unlikely consequences if certain functions in GapP are in #P (where GapP is the class of integer-valued functions that are the difference of two #P functions).  The reference section to [Ikenmeyer, Pak] lists earlier work that also touched on this topic.  One can construct artifical examples of functions in <span class="math-container">$FP^{\#P}$</span> that are complete under poly-time Turing reductions but seem unlikely to be complete under reductions that make only one query.  (For example, you can define a function f such that f(x,y) = PERM(x), where y is a string of length |x| that one builds by asking a series of questions such as &quot;Is g(xz) even or odd&quot; where z is initially the empty string and is built bit-by-bit, depending on the answers to earlier queries.  But this function is unlikely to be in #P.</p>
<p>It is quite conceivable that one could prove a theorem of the form &quot;If Z is true, then functions f and g exist satisfying the conditions you ask about in your question&quot; where Z is some plausible complexity-theoretic condition.  I'm not aware of any theorem of this form that has been proved.</p>

CC BY-SA 4.0
2024-11-21T23:00:53.760Z
2024-11-21T23:00:53.760Z
Eric Allender
<p>I believe this is open, even if you assume <span class="math-container">$\mathsf{FP} \neq \mathsf{\# P}$</span>.</p>
<p>It's closely related to parsimonious reductions. If <span class="math-container">$R,S$</span> are relations defining languages in NP (that is, <span class="math-container">$L_R = \{x : (\exists w)[|w| \leq poly(|x|), (x, w) \in R\}$</span> is in NP). Let <span class="math-container">$\# R(x) = \#\{w : (x,w) \in R \text{ and } |w| \leq poly(|x|)\}$</span>, the number of witnesses that <span class="math-container">$x \in L_R$</span>. A poly-time parsimonious reduction is then a many-one reduction <span class="math-container">$f$</span> - <span class="math-container">$x \in L_R$</span> iff <span class="math-container">$f(x) \in L_S$</span> - that furthermore satisfies <span class="math-container">$\# R(x) = \# S(f(x))$</span>.</p>
<p>Let's call a reduction &quot;weakly parsimonious&quot; (I've seen the concept somewhere before, but don't remember if this is the right name and can't find a reference) if it is like a parsimonious reduction, except that there is additionally a poly-time function <span class="math-container">$h_2$</span> (named to be consistent w/ the OQ) such that <span class="math-container">$\#R(x) = h_2(\#S(f(x)), x)$</span>. If an NP-complete relation/problem is complete under weakly parsimonious reductions, then its associated counting function is <span class="math-container">$\# P$</span>-complete under many-one reductions.</p>
<p>But the analogous question for many-one versus Turing reductions to define <span class="math-container">$\mathsf{NP}$</span>-completeness is open, but they are different assuming <span class="math-container">$\mathsf{NP}$</span> does not have p-measure zero within <span class="math-container">$\mathsf{E}$</span> (Lutz-Mayordomo, see <a href="https://cstheory.stackexchange.com/a/139/129">this answer</a>). It would be interesting to see a resolution of this question under a similar resource-bounded measure assumption.</p>

CC BY-SA 4.0
2024-11-22T22:59:31.523Z
2024-11-22T22:59:31.523Z
Joshua Grochow
<p>The answer to your question is in this paper <a href="https://scholar.google.com/scholar?cluster=11865094586611597999&amp;hl=en&amp;as_sdt=0,33" rel="nofollow noreferrer">Cook reductions blur structural differences between functional complexity classes</a>.</p>

CC BY-SA 4.0
2024-12-02T09:01:52.217Z
This does not answer the question. What the paper calls *Cook[1] reduction* is what is called in this question (and generally known as) *many-one reduction*. What the paper calls *Karp reduction* is what is normally known as *parsimonious reduction*; it is the restricted version of many-one reduction where you additionally assume $h_2$ is the identity. So they show that a specific subclass of #P is #P-complete under many-one reductions, but not under parsimonious reductions, unless P = NP. But the mere existence of such a problem is trivial: e.g., take $f(x)+1$, where $f$ is a #P-complete ...
Emil Jeřábek
CC BY-SA 4.0
2024-12-02T09:04:33.170Z
... problem (this cannot be #P-complete under parsimonious reductions as it never takes the value $0$). For a nonartificial example, the permanent of 0–1 matricies is #P-complete under many-one reductions, but not under parsimonious reductions unless P = NP, as it is decidable in P whether a 0–1 matrix has permanent 0. In any case, this has nothing to do with the question of distinguishing many-one reductions from Turing reductions.
Emil Jeřábek
CC BY-SA 4.0
2024-12-02T00:23:17.277Z
2024-12-02T00:23:17.277Z
Tayfun Pay
<p>I am not aware of any source that compares both notions. Are there two functions in <span class="math-container">$\#P$</span>, say <span class="math-container">$f$</span> and <span class="math-container">$g$</span>, such that <span class="math-container">$f \in \mathbf{FP}^g$</span> but there is no polynomial-time many-one counting reduction from <span class="math-container">$f$</span> to <span class="math-container">$g$</span>?</p>
<p>By the second notion of reduction, I am referring to a pair of polynomial-time computable functions, <span class="math-container">$h_1$</span> and <span class="math-container">$h_2$</span>, such that <span class="math-container">$h_1$</span> transforms instances of <span class="math-container">$f$</span> into instances of <span class="math-container">$g$</span>, and <span class="math-container">$h_2$</span> is a function from <span class="math-container">$\mathbb{N}$</span> to <span class="math-container">$\mathbb{N}$</span> such that <span class="math-container">$f = h_2 \circ g \circ h_1$</span>.</p>
<p><strong>EDIT:</strong></p>
<p>Emil Jeřábek points out that <span class="math-container">$h_2$</span> should also have access to the original input, which I suppose is equivalent to a Turing reduction with a single oracle call.</p>

CC BY-SA 4.0
2024-11-19T12:27:00.967Z
This is a wrong definition of many-one reduction: $h_2$ must have access to the original input as well.
Emil Jeřábek
CC BY-SA 4.0
2024-11-19T15:06:15.470Z
Good point, thank you! I have edited the question.
María Alejandra Schild
<cc.complexity-theory><complexity-classes><counting-complexity><reductions>
Are the notions of #P-completeness via Turing reductions and polynomial many-one counting reductions equivalent?
María Alejandra Schild
# Are the notions of #P-completeness via Turing reductions and polynomial many-one counting reductions equivalent?

(Asked by: username_0 on 2024-11-19)

I am not aware of any source that compares both notions. Are there two functions in $\#P$, say $f$ and $g$, such that $f \in \mathbf{FP}^g$ but there is no polynomial-time many-one counting reduction from $f$ to $g$?

By the second notion of reduction, I am referring to a pair of polynomial-time computable functions, $h\_1$ and $h\_2$, such that $h\_1$ transforms instances of $f$ into instances of $g$, and $h\_2$ is a function from $\mathbb{N}$ to $\mathbb{N}$ such that $f = h\_2 \circ g \circ h\_1$.

**EDIT:**

Emil Jeřábek points out that $h\_2$ should also have access to the original input, which I suppose is equivalent to a Turing reduction with a single oracle call.

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity, reductions
> **Comments:**
> **username_1**: This is a wrong definition of many-one reduction: $h_2$ must have access to the original input as well.  
> **username_0**: Good point, thank you! I have edited the question.  

---

## 3 answers

### Answer by username_2 on 2024-11-21. Score: 3

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 one could prove unconditionally that the answer is "no". I am rather confident that the answer to your question is not known.

Note that there are very likely many functions in $FP^{\#P}$ that are not in #P. There is a recent paper by Ikenmeyer & Pak (FOCS 2022) discussing various unlikely consequences if certain functions in GapP are in #P (where GapP is the class of integer-valued functions that are the difference of two #P functions). The reference section to [Ikenmeyer, Pak] lists earlier work that also touched on this topic. One can construct artifical examples of functions in $FP^{\#P}$ that are complete under poly-time Turing reductions but seem unlikely to be complete under reductions that make only one query. (For example, you can define a function f such that f(x,y) = PERM(x), where y is a string of length |x| that one builds by asking a series of questions such as "Is g(xz) even or odd" where z is initially the empty string and is built bit-by-bit, depending on the answers to earlier queries. But this function is unlikely to be in #P.

It is quite conceivable that one could prove a theorem of the form "If Z is true, then functions f and g exist satisfying the conditions you ask about in your question" where Z is some plausible complexity-theoretic condition. I'm not aware of any theorem of this form that has been proved.


---

### Answer by username_3 on 2024-11-22. Score: 1

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 : (\exists w)[|w| \leq poly(|x|), (x, w) \in R\}$ is in NP). Let $\# R(x) = \#\{w : (x,w) \in R \text{ and } |w| \leq poly(|x|)\}$, the number of witnesses that $x \in L\_R$. A poly-time parsimonious reduction is then a many-one reduction $f$ - $x \in L\_R$ iff $f(x) \in L\_S$ - that furthermore satisfies $\# R(x) = \# S(f(x))$.

Let's call a reduction "weakly parsimonious" (I've seen the concept somewhere before, but don't remember if this is the right name and can't find a reference) if it is like a parsimonious reduction, except that there is additionally a poly-time function $h\_2$ (named to be consistent w/ the OQ) such that $\#R(x) = h\_2(\#S(f(x)), x)$. If an NP-complete relation/problem is complete under weakly parsimonious reductions, then its associated counting function is $\# P$-complete under many-one reductions.

But the analogous question for many-one versus Turing reductions to define $\mathsf{NP}$-completeness is open, but they are different assuming $\mathsf{NP}$ does not have p-measure zero within $\mathsf{E}$ (Lutz-Mayordomo, see [this answer](https://cstheory.stackexchange.com/a/139/129)). It would be interesting to see a resolution of this question under a similar resource-bounded measure assumption.


---

### Answer by username_4 on 2024-12-02. Score: 0

The answer to your question is in this paper [Cook reductions blur structural differences between functional complexity classes](https://scholar.google.com/scholar?cluster=11865094586611597999&hl=en&as_sdt=0,33).

> **Comments:**
> **username_1**: This does not answer the question. What the paper calls *Cook[1] reduction* is what is called in this question (and generally known as) *many-one reduction*. What the paper calls *Karp reduction* is what is normally known as *parsimonious reduction*; it is the restricted version of many-one reduction where you additionally assume $h_2$ is the identity. So they show that a specific subclass of #P is #P-complete under many-one reductions, but not under parsimonious reductions, unless P = NP. But the mere existence of such a problem is trivial: e.g., take $f(x)+1$, where $f$ is a #P-complete ...  
> **username_1**: ... problem (this cannot be #P-complete under parsimonious reductions as it never takes the value $0$). For a nonartificial example, the permanent of 0–1 matricies is #P-complete under many-one reductions, but not under parsimonious reductions unless P = NP, as it is decidable in P whether a 0–1 matrix has permanent 0. In any case, this has nothing to do with the question of distinguishing many-one reductions from Turing reductions.  

---

