questions in NP but not in #P
1 
Are there problems that are in NP class but not in #P class? According to Wiki definition: "More formally, #P is the class of function problems of the form "compute ƒ(x)," where ƒ is the number of accepting paths of a nondeterministic Turing machine running in polynomial time". So I am thinking, if you already have a poly nondeterministic Turing machine that can accept correct paths, then you can just use this to count in poly time. Is there something I am missing here? Thanks.
improve this question | comment
BadgerPriest Created at: 2013-11-15 02:16:51 UTC By BadgerPriest
1 Answer
0 ✓ 
NP is a class of decision problems, while #P is a class of functions. If a function f is in #P then the decision problem L={x:f(x)>0} is in NP.

As far as I know, it is not expected that for every f in #P, the decision problem L={(x,y):f(x)=y} is in NP. In particular, it is not clear how you would verify non-deterministically that a given non-deterministic machine has exactly y (or even at most y or at least y) accepting paths (where y is encoded in binary; if it's encoded in unary, then the task is perfectly possible). Do you have any suggestions?
improve this answer | comment
Your Answer