greg@garnet.berkeley.edu (Greg Kuperberg) (08/01/90)
Eddie Grove mentioned the result of Valiant that computing the permanent of a matrix is #P-complete. I figured that some people might be in the dark about what #P is, so I will communicate the answer which I just found myself. A computational function f(n) whose values are non-negative integers is said to be in #P if there exists a non-deterministic Turing machine (which runs in polynomial time in the length of the input, e.g. the number of bits in n) such that with input n, f(n) of the leaves of the machine behavior tree terminate with the output "Yes". Equivalently, the machine can output non-negative integers upon termination and f(n) should be the sum of all of the outputs. Given a function f(n) whose values are rational numbers between 0 and 1, you could also ask whether or not there exists a polynomial-time probabilistic algorithm that outputs "Yes" with probability f(n) and "No" with probability 1-f(n). This should be an equivalent concept. It is easy to show that the permanent of an integer matrix is in #P. The algorithm guesses one term in the permanent at random and compute it. What is much more exciting is the fact that if the permanent can be computed in polynomial time, everything in #P can be computed in polynomial time. In particular, #P is at least as hard as NP. ----- Greg Kuperberg