1
$\begingroup$

First of all, I'm not a computer scientist so I apologize if this is a stupid question.

I know that the problem of computing the permanent of a matrix is #P-hard, which as I understand it this implies that if you can solve an arbitrary instance of the problem in polynomial time then you can in principle solve any problem in #P in polynomial time.

What I'm wondering is if it also implies being able to solve NP problems in polynomial time (I'm guessing not).

| cite | improve this question | |
$\endgroup$
2
$\begingroup$

Let's take SAT, the quintessential NP-complete problem, as an example. An instance of SAT is a formula, and the answer is whether the formula is satisfiable. The corresponding #P-hard problem #SAT is instead to count the number of satisfying assignment. Clearly if you can count the number of satisfying assignments then you can tell whether one exists. In particular, if you can solve #SAT in polynomial time, you can solve SAT in polynomial time.

This shows that if some #P-hard problem can be computed in polynomial time, then all problems in NP can also be solved in polynomial time.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you. That's very interesting, since it is possible to engineer quantum mechanical systems the measurement probabilities of which are described by the permanent of the system's matrix. That's why I doubted it, it seemed like it would make it theoretically possible to efficiently solve NP-Complete problems on a quantum computer. I suppose the big challenge there is doing it in the general case and not just for once specific instance. Is your statement related to the fact that $NP \subseteq P^{\#P}$? $\endgroup$ – fulis Feb 15 '16 at 7:42
  • $\begingroup$ It's a much easier special case. Toda's theorem shows that the entire polynomial hierarchy can be computed in polynomial time using a #P oracle. $\endgroup$ – Yuval Filmus Feb 15 '16 at 7:53
  • $\begingroup$ Shouldn't #2-sum be #P-hard if $P=NP$? $\endgroup$ – Travis Wells Dec 9 '19 at 22:47

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.