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?


  • 6
    $\begingroup$ 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 $\endgroup$ – Sasho Nikolov Oct 27 '11 at 4:53
  • 2
    $\begingroup$ Just divide any row by $4^{3m}$. $\endgroup$ – MCH Oct 27 '11 at 6:04
  • 3
    $\begingroup$ @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. $\endgroup$ – Suresh Venkat Oct 27 '11 at 18:27
  • 1
    $\begingroup$ @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 :) $\endgroup$ – Sasho Nikolov Oct 28 '11 at 16:56
  • $\begingroup$ @MCH The reduction is not parsimonious. $\endgroup$ – Tayfun Pay Oct 28 '11 at 19:46

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 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.

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

  • $\begingroup$ Is there anything wrong with what @MCH suggested: divide one row by $4^{m}$? Doesn't that make the reduction parsimonious? $\endgroup$ – Sasho Nikolov Oct 28 '11 at 18:11
  • 6
    $\begingroup$ 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). $\endgroup$ – Markus Bläser Oct 28 '11 at 19:13
  • 4
    $\begingroup$ @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. $\endgroup$ – Markus Bläser Oct 28 '11 at 21:21
  • 3
    $\begingroup$ 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.” $\endgroup$ – Tsuyoshi Ito Nov 4 '11 at 21:49
  • 1
    $\begingroup$ @Tsuyoshi: I have seen these reductions been called "weakly parsimonious". $\endgroup$ – Norbert Schuch Nov 6 '11 at 2:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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