<p>What you seem to call a <em>reduction in the classical sense</em> is usually called a <em>parsimonious reduction</em> between counting problems. But there are different possibilities for counting problems. </p>

<p><strong>Parsimonious reduction</strong>: $f$ is reducible to $g$ if there exists a polytime computable function $\rho:\{0,1\}^\star\to\{0,1\}^\star$ such that for every $x\in\{0,1\}^\star$,$f(x)=g(\rho(x))$.</p>

<p><strong>Many-one reduction</strong>:  $f$ is reducible to $g$ if there exist polytime computable functions $\rho:\{0,1\}^\star\to\{0,1\}^\star$ and $\tau:\mathbb N\to\mathbb N$ such that for every $x\in\{0,1\}^\star$, $f(x)=\tau(g(\rho(x)))$.</p>

<p><strong>Oracle reduction</strong>: $f$ is reducible to $g$ if $f(x)$ can be computed in polynomial time using an oracle for $g$ (there is an special oracle tape on your TM such that if $x$ is written, you get $g(x)$ in one step).</p>

<p>Using these definitions (note that some authors may have different names for the same notions), what you are saying is that the classical proofs show that the permanent is $\sharp\mathsf P$-complete for <em>many-one</em> reductions, and not <em>parsimonious</em> reductions. And the question is: Is the permanent $\sharp\mathsf P$-complete for parsimonious reductions?</p>

<p><strike>I do not know a definitive answer to this question, but I wonder if there is a link with the fact that the permanent is NOT $\sharp\mathsf P$-complete in characteristic $2$. If there were a parsimonious reduction, wouldn't it work in characteristic $2$?</strike></p>

<p>The answer to this question has been given in comments by Markus Bläser: The problem of testing the permanent (of a $\{0,1\}$-matrix) for zero is in $\mathsf P$ since it is equivalent to testing the existence of a perfect matching in a bipartite graph.  If the permanent were $\sharp\mathsf P$-complete for parsimonious reductions, this would give an algorithm that associates to each 3-CNF formula a matrix whose permanent is exactly the number of valid assignments of the formula. By testing this permanent for zero, we would know whether the formula is satisfiable or not.</p>

<p><strong>Short answer:</strong> The permanent is $\sharp\mathsf P$-complete under <em>many-one</em> reductions, but not under <em>parsimonious</em> reductions unless $\mathsf P=\mathsf{NP}$. </p>

CC BY-SA 3.0
2011-10-28T18:11:28.387Z
Is there anything wrong with what @MCH suggested: divide one row by $4^{m}$? Doesn't that make the reduction parsimonious?
Sasho Nikolov
CC BY-SA 3.0
2011-10-28T19:13:20.223Z
It depends which entries you allow in the matrix. Permanent over $\{0,1\}$ is #P-complete under many-one-reductions, but cannot be complete under parsimonious reductions unless P = NP. Permanent over the rationals is not in #P (for syntactic reasons).
Markus Bläser
CC BY-SA 3.0
2011-10-28T19:46:09.617Z
The problem is that there isnt a concrete definition of these reductions. Sometimes people call the same reduction something else and it confuses everyone. As far as I know, Permanent {0,1} is #P-Complete under Cook-like reductions, that is Oracle reductions. It is not complete under Karp-like reductions nor Parsimonious reductions. Otherwise, P would equal NP.
Tayfun Pay
CC BY-SA 3.0
2011-10-28T20:53:26.043Z
@MarkusBläser I see. Is the problem then the characteristic 2 issue? What I can see is that if there were a parsimonious reduction from #3SAT to permanent, then we could solve Unique-SAT in poly time, and by Valiant-Vazirani NP = RP. How can you show that a parsimonious reduction would imply NP = P?
Sasho Nikolov
CC BY-SA 3.0
2011-10-28T21:21:56.307Z
@Sasho: You can check whether the permanent of a {0,1}-matrix is nonzero by computing a maximum matching. If there were a parsimonious reduction from #3SAT to the permanent, then you could check in polynomial time whether there is a satisfying assignment.
Markus Bläser
CC BY-SA 3.0
2011-10-29T01:14:11.703Z
@MarkusBläser thanks! I missed the simple solution i guess
Sasho Nikolov
CC BY-SA 3.0
2011-11-04T21:49:21.427Z
Are the reductions of the second kind really called “many-one reductions”?  I would avoid that term because in case of decision problems, many-one reductions are not allowed to change the answer between yes and no.  I call them “functional reductions” or “Levin reductions.”
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-06T02:42:03.507Z
@Tsuyoshi: I have seen these reductions been called "weakly parsimonious".
Norbert Schuch
CC BY-SA 3.0
2011-11-06T03:21:31.850Z
I realized that functional (or Levin) reductions are something different from what is called “many-one reductions” in this answer.  In functional reductions, mapping τ takes both x and g(ρ(x)).
Tsuyoshi Ito
CC BY-SA 3.0
2011-10-28T16:30:18.843Z
2011-11-03T21:05:40.023Z
2011-11-03T21:05:40.023Z
Bruno
<p>Just to clarify, Valiant's proof does the following:</p>

<p>Given $\phi$ a #3SAT instance with m clauses and n vars, Valiant constructs a matrix whose permanent is $4^{3m}\#\phi$. Now, this is NOT a reduction in the classical sense, but rather there's some post processing required (i.e. I don't get $\#\phi$, but I have to divide by $4^{3m}$.</p>

<p>Am I misunderstanding something, or is this correct?</p>

<p>Thanks!</p>

CC BY-SA 3.0
2011-10-27T04:53:04.133Z
for decision problems, a Karp reduction is enough: just a poly-time computable map from yes instances of one language to yes instances of another. for function problems, you need at least two poly time computable maps: one that maps instances $I_1$ of problem $P_1$ to instance $I_2$ of problem $P_2$ and another that maps the solution of $I_2$ to a correct solution of $I_1$. so this is fairly standard: you never aim for exact equality of solutions. also, this way you can have reductions between problems with different solution spaces
Sasho Nikolov
CC BY-SA 3.0
2011-10-27T06:04:23.590Z
Just divide any row by $4^{3m}$.
Mahdi Cheraghchi
CC BY-SA 3.0
2011-10-27T18:27:14.093Z
@SashoNikolov You should post your comment as an answer. You'll get credit for it, and if appropriate it can be marked as an accepted answer. This will also prevent the question from being automatically reposted periodically by the Community bot.
Suresh Venkat
CC BY-SA 3.0
2011-10-28T16:56:48.133Z
@SureshVenkat I didn't, at first, because I actually thought that the question might get closed. Now I think Bruno's answers is much more detailed than my comment, so I'll upvote him :)
Sasho Nikolov
CC BY-SA 3.0
2011-10-28T19:46:41.613Z
@MCH The reduction is not parsimonious.
Tayfun Pay
CC BY-SA 4.0
2021-11-12T17:22:24.277Z
A point of information here: Valiant's reduction ([according to wikipedia](https://en.wikipedia.org/wiki/♯P-completeness_of_01-permanent#Constructing_the_integer_graph)) produces a matrix with entries in $\{-1,0,1,2,3\}$.  (Note that unless P=NP there is no polytime reduction that, given a #3SAT instance $\phi$, produces a *non-negative* matrix whose permanent is $4^{3m}\#\phi$, because testing whether $\#\phi$ is zero is co-NP hard , but testing whether the permanent of a non-negative matrix is zero is in P.)
Neal Young
<cc.complexity-theory><counting-complexity>
Permanent is #P Complete
Anonymous Coward
# Permanent is #P Complete

(Asked by: username_0 on 2011-10-27)

Just to clarify, Valiant's proof does the following:

Given $\phi$ a #3SAT instance with m clauses and n vars, Valiant constructs a matrix whose permanent is $4^{3m}\#\phi$. Now, this is NOT a reduction in the classical sense, but rather there's some post processing required (i.e. I don't get $\#\phi$, but I have to divide by $4^{3m}$.

Am I misunderstanding something, or is this correct?

Thanks!

**Tags:** cc.complexity-theory, counting-complexity

> **Comments:**
> **username_1**: for decision problems, a Karp reduction is enough: just a poly-time computable map from yes instances of one language to yes instances of another. for function problems, you need at least two poly time computable maps: one that maps instances $I_1$ of problem $P_1$ to instance $I_2$ of problem $P_2$ and another that maps the solution of $I_2$ to a correct solution of $I_1$. so this is fairly standard: you never aim for exact equality of solutions. also, this way you can have reductions between problems with different solution spaces  
> **username_2**: Just divide any row by $4^{3m}$.  
> **username_3**: @SashoNikolov You should post your comment as an answer. You'll get credit for it, and if appropriate it can be marked as an accepted answer. This will also prevent the question from being automatically reposted periodically by the Community bot.  
> **username_1**: @SureshVenkat I didn't, at first, because I actually thought that the question might get closed. Now I think username_6's answers is much more detailed than my comment, so I'll upvote him :)  
> **username_4**: @MCH The reduction is not parsimonious.  
> **username_5**: A point of information here: Valiant's reduction ([according to wikipedia](https://en.wikipedia.org/wiki/♯P-completeness_of_01-permanent#Constructing_the_integer_graph)) produces a matrix with entries in $\{-1,0,1,2,3\}$.  (Note that unless P=NP there is no polytime reduction that, given a #3SAT instance $\phi$, produces a *non-negative* matrix whose permanent is $4^{3m}\#\phi$, because testing whether $\#\phi$ is zero is co-NP hard , but testing whether the permanent of a non-negative matrix is zero is in P.)  

---

## 1 answers

### Answer by username_6 on 2011-10-28. Score: 12

What you seem to call a *reduction in the classical sense* is usually called a *parsimonious reduction* between counting problems. But there are different possibilities for counting problems.

**Parsimonious reduction**: $f$ is reducible to $g$ if there exists a polytime computable function $\rho:\{0,1\}^\star\to\{0,1\}^\star$ such that for every $x\in\{0,1\}^\star$,$f(x)=g(\rho(x))$.

**Many-one reduction**: $f$ is reducible to $g$ if there exist polytime computable functions $\rho:\{0,1\}^\star\to\{0,1\}^\star$ and $\tau:\mathbb N\to\mathbb N$ such that for every $x\in\{0,1\}^\star$, $f(x)=\tau(g(\rho(x)))$.

**Oracle reduction**: $f$ is reducible to $g$ if $f(x)$ can be computed in polynomial time using an oracle for $g$ (there is an special oracle tape on your TM such that if $x$ is written, you get $g(x)$ in one step).

Using these definitions (note that some authors may have different names for the same notions), what you are saying is that the classical proofs show that the permanent is $\sharp\mathsf P$-complete for *many-one* reductions, and not *parsimonious* reductions. And the question is: Is the permanent $\sharp\mathsf P$-complete for parsimonious reductions?

I do not know a definitive answer to this question, but I wonder if there is a link with the fact that the permanent is NOT $\sharp\mathsf P$-complete in characteristic $2$. If there were a parsimonious reduction, wouldn't it work in characteristic $2$?

The answer to this question has been given in comments by username_7: The problem of testing the permanent (of a $\{0,1\}$-matrix) for zero is in $\mathsf P$ since it is equivalent to testing the existence of a perfect matching in a bipartite graph. If the permanent were $\sharp\mathsf P$-complete for parsimonious reductions, this would give an algorithm that associates to each 3-CNF formula a matrix whose permanent is exactly the number of valid assignments of the formula. By testing this permanent for zero, we would know whether the formula is satisfiable or not.

**Short answer:** The permanent is $\sharp\mathsf P$-complete under *many-one* reductions, but not under *parsimonious* reductions unless $\mathsf P=\mathsf{NP}$.

> **Comments:**
> **username_1**: Is there anything wrong with what @MCH suggested: divide one row by $4^{m}$? Doesn't that make the reduction parsimonious?  
> **username_7**: It depends which entries you allow in the matrix. Permanent over $\{0,1\}$ is #P-complete under many-one-reductions, but cannot be complete under parsimonious reductions unless P = NP. Permanent over the rationals is not in #P (for syntactic reasons).  
> **username_4**: The problem is that there isnt a concrete definition of these reductions. Sometimes people call the same reduction something else and it confuses everyone. As far as I know, Permanent {0,1} is #P-Complete under Cook-like reductions, that is Oracle reductions. It is not complete under Karp-like reductions nor Parsimonious reductions. Otherwise, P would equal NP.  
> **username_1**: @MarkusBläser I see. Is the problem then the characteristic 2 issue? What I can see is that if there were a parsimonious reduction from #3SAT to permanent, then we could solve Unique-SAT in poly time, and by Valiant-Vazirani NP = RP. How can you show that a parsimonious reduction would imply NP = P?  
> **username_7**: @Sasho: You can check whether the permanent of a {0,1}-matrix is nonzero by computing a maximum matching. If there were a parsimonious reduction from #3SAT to the permanent, then you could check in polynomial time whether there is a satisfying assignment.  
> **username_1**: @MarkusBläser thanks! I missed the simple solution i guess  
> **username_8**: Are the reductions of the second kind really called “many-one reductions”?  I would avoid that term because in case of decision problems, many-one reductions are not allowed to change the answer between yes and no.  I call them “functional reductions” or “Levin reductions.”  
> **username_9**: @Tsuyoshi: I have seen these reductions been called "weakly parsimonious".  
> **username_8**: I realized that functional (or Levin) reductions are something different from what is called “many-one reductions” in this answer.  In functional reductions, mapping τ takes both x and g(ρ(x)).  

---

