8
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ This is a wrong definition of many-one reduction: $h_2$ must have access to the original input as well. $\endgroup$
    – Emil Jeřábek
    Commented Nov 19 at 12:27
  • $\begingroup$ Good point, thank you! I have edited the question. $\endgroup$
    – María Alejandra Schild
    Commented Nov 19 at 15:06

3 Answers 3

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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). It would be interesting to see a resolution of this question under a similar resource-bounded measure assumption.

Improve this answer
$\endgroup$
0
$\begingroup$

The answer to your question is in this paper Cook reductions blur structural differences between functional complexity classes.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 ... $\endgroup$
    – Emil Jeřábek
    Commented Dec 2 at 9:01
  • $\begingroup$ ... 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. $\endgroup$
    – Emil Jeřábek
    Commented Dec 2 at 9:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.