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)
