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?
Created at: 2013-11-15 02:17:41 UTC
By Guest