# Problems in NP but not in #P

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?

• The verifier for an NP problem has no way of knowing how many valid certificates there are, it just recognize any valid one. – G. Bach Nov 14 '13 at 19:39

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?

• The decision problem : "Given $F$, a CNF formula, and $k$ a positive integer, is it true that $F$ has at least $k$ models ?" is known to be PP-complete thus is not in NP (unless $P=NP$). – Xavier Labouze Nov 15 '13 at 11:36

The simple answer to your question is "Yes, all of them!" No problem in NP is in #P because NP is a class of decision problems (problems where the answer is yes or no: for example, is this graph 3-colourable?), but #P is a class of function problems (problems where the answer is a non-negative integer: for example, how many 3-colourings does this graph have?).

You seem to be confused about the basic definitions. A decision problem is in NP if there is a nondeterministic, polynomial-time Turing machine that has at least one accepting path whenever the answer is "yes" and no accepting paths whenever the answer is "no". A function problem $f$ is in #P exactly when there is a nondeterministic, polynomial-time Turing machine that has exactly $f(x)$ accepting paths for every input $x$. So, NP is about the existence of accepting paths, while #P is about the number of them.

I'm not sure what you mean by "if you already have a [...] Turing machine that can accept correct paths". Turing machines don't accept paths — they accept (or reject) their input. An accepting path of a Turing machine is a computation that it makes, that ends in an accepting state.

1. For every function $f$ in #P, the decision problem "Is $f(x)>0$?" is in NP. This is because the Turing machine that computes $f$ (in the sense that it has $f(x)$ accepting paths for every input $x$) has at least one accepting path (i.e., accepts its input in the sense of NP) exactly when $f(x)>0$.
2. Every decision problem in NP is contained in P#P. That is, if you have an oracle for any #P-complete problem, you can use it to answer any NP decision problem. This is because every problem in NP is accepted by some Turing machine $M$. The machine $M$ computes some function $f$, where $f(x)$ is the number of accepting paths that $M$ has for input $x$. So, to find out if $M$ has at least one accepting path, you just use the oracle to compute $f(x)$ and then check if that value is greater than zero.
• In bullet points 1 and 2, it is maybe a bit confusing to say "the TM that computes $f$ (in the sense that it has $f(x)$ accepting paths on input $x$)." Normally, we think of a machine computing a function as taking an input $x$ and outputting a value $f(x)$. Maybe a better phrasing is "the TM representing $f$ (in the sense that...)". – usul Nov 19 '13 at 1:47