<p>This is a very interesting question. </p>

<p>First, a clarifying remark. Note that "upper bound on the number of witnesses" is <strong>not</strong> 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).</p>

<p>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$. </p>

<p>All I think I can say at the moment is this: </p>

<ol>
<li>Every $NP$-complete problem I know (defined by some natural verifier) has an obvious corresponding $\#P$-complete counting version (with the <em>same</em> verifier). </li>
<li>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.</li>
</ol>

<p>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 </p>

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

<p>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 <em>know</em> 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$.</p>

<p>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)]}$. </p>

<p>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 <em>separations</em> are unlikely, but it seems unlikely they'd be proved by giving a subexp time $NP$-oracle algorithm for the Permanent. </p>

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

CC BY-SA 3.0
2014-11-15T09:34:32.650Z
Indeed it is insightful answer.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-11-15T03:00:31.750Z
2014-11-17T04:29:05.683Z
2014-11-17T04:29:05.683Z
Ryan Williams
<p><a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#fewp">FewP</a> 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. </p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>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).</p>

<p><strong>EDIT:</strong> 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).</p>

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

CC BY-SA 3.0
2014-11-02T13:23:47.797Z
Can you give some reference of fewP?  Is the unique-SAT in it: http://wwwnew.cs.princeton.edu/courses/archive/fall05/cos528/handouts/NP_is_as.pdf?
Yixin Cao
CC BY-SA 3.0
2014-11-02T17:00:19.197Z
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}$).
Joshua Grochow
CC BY-SA 3.0
2014-11-03T02:44:48.653Z
Would a padding of SAT answer your question?
Kaveh
CC BY-SA 3.0
2014-11-03T09:12:55.703Z
@Kaveh No, padded SAT instances are artificial.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-11-03T10:31:40.037Z
Is $\text{FewP}$ and sparse density equivalent? Can we rule out the possibility where a dense language, has more than polynomially many witnesses for some input for all provers?


Also, if a language has sparse density, isn't it automatically in $\text{P/poly}$, since we can use the list of accepted inputs as the advice for each input size? Thus, having an $\text{NP}$-complete problem in $\text{FewP}$ is equivalent to the Karp-Lipton theorem, thus unlikely?
chazisop
CC BY-SA 3.0
2014-11-03T10:40:08.600Z
@chazisop No, they are not equivalent.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-11-08T18:44:37.747Z
@chazisop Also, for sparse languages Mahaney's theorem would work better: http://blog.computationalcomplexity.org/2011/09/mahaneys-theorem.html
domotorp
CC BY-SA 3.0
2014-11-08T18:47:07.197Z
@Kaveh Although Mohammad is not interested in your solution, I am curious how that padding argument would work.
domotorp
CC BY-SA 3.0
2014-11-08T19:23:06.750Z
Note that 3-SAT with m clauses has input size O(m log n) which is superlinear in n. So the number of assignments - $2^n$ is already subexponential in input size. To make this even more pronounced consider Circuit-SAT with poly(n) gates. Here input size is poly(n) while the number of witnesses is $2^n$. So the question needs to be rephrased - the number of witnesses is subexponential in what?
daniello
CC BY-SA 3.0
2014-11-08T19:28:13.837Z
@daniello The input size is the number of variables.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-11-08T19:36:37.820Z
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.
daniello
CC BY-SA 3.0
2014-11-08T19:56:07.187Z
@MohammadAl-Turkistany Aren't you referring to complexity class ${\bf EP}$ defined in the paper "Restrictive Acceptance Suffices for Equivalence Problems" ?
Tayfun Pay
CC BY-SA 3.0
2014-11-08T20:30:15.173Z
@TayfunPay I am not sure if $EP$ is a superclass of mine.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-11-08T20:36:19.410Z
@domotorp, I was thinking of something simple like SAT instances with $n^k$ $p \lor \lnot p$ clauses added. It is still NP-complete and if SAT can be solved in time $t(n)$ then $n^k$-Pad-SAT can be solved in $t(n^{\frac{1}{k}}) + O(n)$.
Kaveh
CC BY-SA 3.0
2014-11-08T20:59:55.007Z
@Kaveh I don't think your example is subexponential. See definition at https://complexityzoo.uwaterloo.ca/Complexity_Zoo:S#subexp
domotorp
CC BY-SA 3.0
2014-11-08T21:00:15.997Z
@daniello Same about your example.
domotorp
CC BY-SA 3.0
2014-11-08T21:19:24.377Z
@domotorp in your link n is the number of input bits, which is not the case in my examples. I'm just pointing out that the $n$ is an arbitrary letter chosen to measure the number of vertices in a graph / variables in a formula, and that for the question to make sense one has to be able to arrive at the meaning of $n$ from the definition of the language. Otherwise one could always decide to say that n is the bitlength of the np witness - maybe that is what Mohammad actually means, but then this should be put into the question...
daniello
CC BY-SA 3.0
2014-11-08T21:30:40.407Z
@daniello I understand what you are saying but your definition of subexponential is not the one usually used in TCS. According to my link $2^n$ is NOT subexponential in $n^2$.
domotorp
CC BY-SA 3.0
2014-11-08T21:53:39.547Z
@domotorp you are absolutely right - it seems like the definition of subexponential differs between the complexity zoo and how it is usually used in exact exponential time algorithms / parameterized algorithms (see the literature on the exponential time hypothesis). With this interpretation of subexponential the question makes perfect sense too.
daniello
CC BY-SA 3.0
2014-11-09T11:28:21.943Z
@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.
domotorp
CC BY-SA 3.0
2014-11-09T20:38:57.910Z
@downvoters Why the hell are people downvoting this question? I mean at least someone could give a reason for it...
domotorp
CC BY-SA 3.0
2014-11-09T23:02:27.807Z
@domotrop, the question is NOT about the complexity class. You interpreted the question in one way, I interpreted in another way. I think asking for natural problems makes sense with my interpretation. OP can clarify what he wants, I am not sure you are insisting on your interpretation when it does not follow from the question. Even restricted to complexity theory the term subexponential is used for various notions, just do a Google scholar search.
Kaveh
CC BY-SA 3.0
2014-11-09T23:12:07.553Z
@Kaveh domotorp's interpretation of my question is accurate.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-11-09T23:15:32.570Z
@Kaveh do you have a reference where it was declared open problem?
Mohammad Al-Turkistany
<cc.complexity-theory><np>
$NP$-complete problem with quasi-polynomial bound on the number of solutions
Mohammad Al-Turkistany
# $NP$-complete problem with quasi-polynomial bound on the number of solutions

(Asked by: username_0 on 2014-11-02)

[FewP](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#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.

**Tags:** cc.complexity-theory, np
> **Comments:**
> **username_1**: Can you give some reference of fewP?  Is the unique-SAT in it: http://wwwnew.cs.princeton.edu/courses/archive/fall05/cos528/handouts/NP_is_as.pdf?  
> **username_2**: 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}$).  
> **username_3**: Would a padding of SAT answer your question?  
> **username_0**: @Kaveh No, padded SAT instances are artificial.  
> **username_4**: Is $\text{FewP}$ and sparse density equivalent? Can we rule out the possibility where a dense language, has more than polynomially many witnesses for some input for all provers?   Also, if a language has sparse density, isn't it automatically in $\text{P/poly}$, since we can use the list of accepted inputs as the advice for each input size? Thus, having an $\text{NP}$-complete problem in $\text{FewP}$ is equivalent to the Karp-Lipton theorem, thus unlikely?  
> **username_0**: @chazisop No, they are not equivalent.  
> **username_5**: @chazisop Also, for sparse languages Mahaney's theorem would work better: http://blog.computationalcomplexity.org/2011/09/mahaneys-theorem.html  
> **username_5**: @Kaveh Although Mohammad is not interested in your solution, I am curious how that padding argument would work.  
> **username_6**: Note that 3-SAT with m clauses has input size O(m log n) which is superlinear in n. So the number of assignments - $2^n$ is already subexponential in input size. To make this even more pronounced consider Circuit-SAT with poly(n) gates. Here input size is poly(n) while the number of witnesses is $2^n$. So the question needs to be rephrased - the number of witnesses is subexponential in what?  
> **username_0**: @daniello The input size is the number of variables.  
> **username_6**: 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.  
> **username_7**: @MohammadAl-Turkistany Aren't you referring to complexity class ${\bf EP}$ defined in the paper "Restrictive Acceptance Suffices for Equivalence Problems" ?  
> **username_0**: @TayfunPay I am not sure if $EP$ is a superclass of mine.  
> **username_3**: @domotorp, I was thinking of something simple like SAT instances with $n^k$ $p \lor \lnot p$ clauses added. It is still NP-complete and if SAT can be solved in time $t(n)$ then $n^k$-Pad-SAT can be solved in $t(n^{\frac{1}{k}}) + O(n)$.  
> **username_5**: @Kaveh I don't think your example is subexponential. See definition at https://complexityzoo.uwaterloo.ca/Complexity_Zoo:S#subexp  
> **username_5**: @daniello Same about your example.  
> **username_6**: @domotorp in your link n is the number of input bits, which is not the case in my examples. I'm just pointing out that the $n$ is an arbitrary letter chosen to measure the number of vertices in a graph / variables in a formula, and that for the question to make sense one has to be able to arrive at the meaning of $n$ from the definition of the language. Otherwise one could always decide to say that n is the bitlength of the np witness - maybe that is what Mohammad actually means, but then this should be put into the question...  
> **username_5**: @daniello I understand what you are saying but your definition of subexponential is not the one usually used in TCS. According to my link $2^n$ is NOT subexponential in $n^2$.  
> **username_6**: @domotorp you are absolutely right - it seems like the definition of subexponential differs between the complexity zoo and how it is usually used in exact exponential time algorithms / parameterized algorithms (see the literature on the exponential time hypothesis). With this interpretation of subexponential the question makes perfect sense too.  
> **username_5**: @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.  
> **username_5**: @downvoters Why the hell are people downvoting this question? I mean at least someone could give a reason for it...  
> **username_3**: @domotrop, the question is NOT about the complexity class. You interpreted the question in one way, I interpreted in another way. I think asking for natural problems makes sense with my interpretation. OP can clarify what he wants, I am not sure you are insisting on your interpretation when it does not follow from the question. Even restricted to complexity theory the term subexponential is used for various notions, just do a Google scholar search.  
> **username_0**: @Kaveh domotorp's interpretation of my question is accurate.  
> **username_0**: @Kaveh do you have a reference where it was declared open problem?  

---

## 1 answers

### Answer by username_8 on 2014-11-15. Score: 11 | Accepted answer

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.

> **Comments:**
> **username_0**: Indeed it is insightful answer.  

---

