Talk:Sharp-P

From Wikipedia, the free encyclopedia

	This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
Start	rated as start-Class on the assessment scale
Mid	rated as mid-importance on the assessment scale

[edit] 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.

[edit] NP-hardness of problems in #P

The sentence "Therefore, the #P problem corresponding to any NP-Complete problem must be NP-Hard" is incorrect. We cannot compare apples and oranges: a problem in #P is a counting problem, whereas any NP-hard problem is a decision problem. The only way to relate them is by oracles, what is done in Toda's theorem.--Miki Hermann 16:02, 24 October 2007 (UTC)