HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Problems in NP but not in #P

Submitted by: @import:stackexchange-cs··
0
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?

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?

Context

StackExchange Computer Science Q#18026, answer score: 7

Revisions (0)

No revisions yet.