patternMinor
Problems in NP but not in #P
Viewed 0 times
problemsnotbut
Problem
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?
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?
Solution
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?
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?
Context
StackExchange Computer Science Q#18026, answer score: 7
Revisions (0)
No revisions yet.