15
$\begingroup$

FewP is the class of $NP$-problems with polynomial bound on the number of solutions (in the input size). There is no known $NP$-complete problem in $fewP$. I am interested in how far we can stretch this observation.

Is there any natural $NP$-complete problem with quasi-polynomial upper bound on the number of solutions (witnesses)? Is there a widely accepted conjecture that would rule out such possibility?

Natural means that the problem is not an artificially made up problem to answer the question (or similar ones) and people are interested in the problem independently (as defined by Kaveh).

EDIT: The bounty will be awarded to such natural $NP$-complete problem or a reasonable argument ruling out the existence of such problems (using widely accepted complexity-theoretic conjectures).

Motivation: My intuition is that $NP$-completeness imposes super-polynomial (or even exponential) lower bound on the number of witnesses.

$\endgroup$
  • 1
    $\begingroup$ The promise problem UniqueSAT is in $\mathsf{PromiseUP}$ (not the same as $\mathsf{UP}$), which is a subset of $\mathsf{PromiseFewP}$ (not the same as $\mathsf{FewP}$). $\endgroup$ – Joshua Grochow Nov 2 '14 at 17:00
  • 3
    $\begingroup$ Would a padding of SAT answer your question? $\endgroup$ – Kaveh Nov 3 '14 at 2:44
  • 1
    $\begingroup$ That is the whole point - it is not; the input size is the number of bits in input, and (sparse) 3-sat instances have size $m \log n$. The number of variables is just one aspect (parameter) of the input, so for other problems (say graph problems) one would have to specify what one is measuring the number of witnesses in terms of. For example for max cut the input graph can have $n^2$ edges, and again there are only $2^n$ witnesses (which is subexponential in input size). But we really want to measure in terms of $n$. However it is not obvious that the #vertices is the right measure. $\endgroup$ – daniello Nov 8 '14 at 19:36
  • 2
    $\begingroup$ @Kaveh Yes, so you should assume that Mohammad thought of the one that makes sense in his question. Also, as you can see, complexity zoo agrees with my definition. In general, in any interesting complexity class the definition should not change if you pad the input by a polynomial. $\endgroup$ – domotorp Nov 9 '14 at 11:28
  • 5
    $\begingroup$ @downvoters Why the hell are people downvoting this question? I mean at least someone could give a reason for it... $\endgroup$ – domotorp Nov 9 '14 at 20:38
11
+50
$\begingroup$

This is a very interesting question.

First, a clarifying remark. Note that "upper bound on the number of witnesses" is not a property of a computational problem per se, but of a particular verifier used to decide an $NP$ problem, just as an "upper bound on number of states" would not be a property of a problem but of a Turing machine deciding it. So saying "$NP$ problem with upper bound on number of solutions" isn't quite accurate, and if $P = NP$ then every $NP$ problem has a verifier with any number of desired solutions (including zero, and including all possible strings).

So we have to make a definition, to address your question. For $s : {\mathbb N} \rightarrow {\mathbb N}$, let's say an $NP$ problem $L$ "has at most $s(n)$ solutions" if for some constant $c$ there is an $O(n^c)$ time verifier $V$ such that, for every input length $n$ and for every $x \in L$ of length $n$, there are distinct $y_1,\ldots,y_{s(n)}$ of length $n^c$ such that $V(x,y_i)$ accepts for all $i$, and $V(x,y)$ rejects all other $y$ of length $n^c$.

All I think I can say at the moment is this:

  1. Every $NP$-complete problem I know (defined by some natural verifier) has an obvious corresponding $\#P$-complete counting version (with the same verifier).
  2. For any $NP$-complete problem defined with a verifier having at most $poly(n)$ solutions (or even $2^{n^{o(1)}}$ solutions) the corresponding counting version probably isn't $\#P$-complete.

More details: Suppose $L$ is $NP$-complete, with a verifier $V$ that has at most $O(n^c)$ solutions. Then the natural counting "decision" version of $L$, which we define as

$Count_L(x) := \text{the number of $y$ such that $V(x,y)$ accepts}$

is computable in $FP^{NP[O(\log n)]}$, that is, a polytime function with $O(\log n)$ queries to $NP$. That is because deciding whether the number of solutions to $x$ is at most $k$ is in $NP$: the witness, if it exists, is simply the number of $y_i$'s making $V$ accept, which we know to be at most $O(n^c)$. Then we can binary search using this $NP$ problem to compute the exact number of solutions to $L$.

Therefore, an $NP$-complete problem of this kind could not be extended to a $\#P$-complete problem in the usual way, unless $\#P \subseteq FP^{NP[O(\log n)]}$. This looks unlikely; the whole polynomial time hierarchy would basically collapse to $P^{NP[O(\log n)]}$.

If you assume $s(n) = 2^{n^{o(1)}}$ in the above, you would still get an unlikely consequence. You would show that $\#P$ can be computed in $2^{n^{o(1)}}$ time with an $NP$ oracle. That's more than enough to prove, for instance, that $EXP^{NP} \neq PP$ and subsequently $EXP^{NP} \not\subset P/poly$. Not that those separations are unlikely, but it seems unlikely they'd be proved by giving a subexp time $NP$-oracle algorithm for the Permanent.

By the way, I have said nothing too insightful here. There is almost certainly an argument like this in the literature.

$\endgroup$

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.