3
$\begingroup$

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?

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

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?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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$). $\endgroup$ – Xavier Labouze Nov 15 '13 at 11:36
2
$\begingroup$

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.

Here are two facts that you might have been thinking about when you asked your question.

  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.
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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...)". $\endgroup$ – usul Nov 19 '13 at 1:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.