Talk:Sharp-P

From Wikipedia, the free encyclopedia

You have new messages (last change).

The following was changed:

"a problem is in #P if there is a non-deterministic, polynomial-time Turing machine that, for each instance I of the problem, has a number of accepting computations that is exactly equal to the number of distinct solutions for instance I.

This is incorrect. A regular NP machine for, say SAT may have many accepting paths, "exactly equal to the number of distinct solutions". A #P Turing machine is a FUNCTIONAL machine. Its a machine that outputs the value of a function f:{0,1}* -> Z such that f(x) = # of solutions.

Retrieved from "http://en.wikipedia.org../../../s/h/a/Talk%7ESharp-P_ab02.html"