2
$\begingroup$

From Wikipedia on $\mathrm{NP}$-completenes: "a [decision] problem is NP-complete if it is both in NP and NP-hard." [link] I think we can paraphrase this as the first statement:

  • An $\mathrm{NP}$-hard (decision) problem $\Pi$ is $\mathrm{NP}$-complete if and only if $\Pi \in \mathrm{NP}$.

  • $\#\mathrm P$-complete (counting) problems are at least as hard as $\mathrm{NP}$-complete problems.

The second statement is from Wikipedia on $\#\mathrm P$-completeness [link].

I think it is fair to conclude that: The two classes of $\mathrm{NP}$-hard and $\#\mathrm P$-complete cannot intersect, since they are defined for fundamentally different types of problems (counting vs decision). However, the second statements suggests that there is a relation between the two. Can this relation be expressed intuitively, like in terms of intersection?


After further reading on the $\#\mathrm P$ class, for which Wikipedia says that it is "the set of the counting problems associated with the decision problems in the set NP," I suspect that the following taxonomy can be established:

enter image description here

Is this correct?

$\endgroup$
1
  • $\begingroup$ Your diagram suggests that $\mathsf{P}\neq\mathsf{NP}$ which is unknown. $\endgroup$
    – Nathaniel
    Oct 3, 2022 at 20:06

1 Answer 1

4
$\begingroup$

The theory of NP-completeness studies decision problems and (indirectly) optimization problems. In contrast, the theory of #P-completeness studies counting problems. In particular, NP is a class of decision problems while #P is a class of counting problems. The elements of these two classes are different, so you cannot compare them directly as your Venn diagram suggests.

Instead of giving precise definitions of the various types of problems, here are some examples:

  • Decision problem (SAT): Given a CNF, determine whether it is satisfiable.
  • Counting problem (#SAT): Given a CNF, determine the number of satisfying assignment.
  • Optimization problem (MAX-SAT): Given a CNF, determine the maximum number of clauses which can be satisfied simultaneously.

If you can solve #SAT efficiently then you can solve SAT efficiently. This is not an isolated case. Recall that a decision problem $L$ is in NP if there is a polynomial time verifier $V$ and a constant $C$ such that $$ L = \{ x : V(x,y) = 1 \text{ for some } y \text{ of length at most } C|x|^C \}. $$ A counting problem $f$ (which maps instances to natural numbers) is in #P if there is a polynomial time verifier $V$ and a constant $C$ such that $$ f(x) = |\{ y \text{ of length at most } C|x|^C : V(x,y) = 1\}|. $$ That is, $f(x)$ counts the number of witnesses for $x$. For a given verifier $V$, computing $f(x)$ is harder than deciding whether $x \in L$, since $x \in L$ iff $f(x) \geq 1$.

This suggests that if a decision problem is hard, then its counting version is also hard. The converse is not true. For example, 2SAT (the special case of SAT in which all clauses contain at most two literals) is in P, but its counting version #2SAT is #P-complete.


Where do optimization problem fit in? We can think of an optimization problem as given by a verifier $V(x,y)$ which checks whether $y$ is a feasible solution for $x$, together with a function $O(x,y)$ which computes the objective value of $y$. For example, in MAX-SAT, $V(x,y)$ checks that $y$ is a truth assignment for the variables appearing in the CNF $x$, and $O(x,y)$ counts the number of clauses of $x$ satisfied by $y$. We can associate with each maximization problem the following decision version: $$ \{ (x,o) : V(x,y) = 1 \text{ and } O(x,y) \geq o \text{ for some } y \text{ of length at most } C|x|^C \}. $$ In the case of MAX-SAT, we are given a CNF $x$ and a target $o$, and we need to determine whether some truth assignment satisfies at least $o$ clauses of $x$.

We say that an optimization problem is NP-hard if its decision version is NP-hard. In the case of MAX-SAT, the problem is obviously NP-hard, since choosing $o$ to be the number of clauses reduces the problem to SAT. (In fact, even MAX-2SAT is NP-hard, although 2SAT itself is in P.) In many other cases (for example, Vertex Cover, Max Cut and so on), there is no natural decision problem (no analog of SAT) other than the one obtained from the optimization problem.

$\endgroup$
1
  • $\begingroup$ Right, that was a bad choice... $\endgroup$ Oct 4, 2022 at 8:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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