Reading the question Natural NP-Complete Problems with Large Witnesses, I was interested in this language:

$L = \{ \varphi ~~:~~ \varphi \text{ is SAT formula with more than } |\varphi|^2 \text{ satisfying assignments}\}$

It made me think of the following generalization. Let $A$ be a language in $\textsf{NP}$ and fix a corresponding verifier machine $M$. My question is, What is known about the language consisting of members of $A$ that have at least $f(n)$ witnesses (where $n$ is the size of the input and witnesses are relative to the verifier $M$)?


More formally: We have a deterministic polynomial-time verifier $M$, so a witness of $a \in A$ relative to $M$ is a string $w$ such that $M(a,w) = 1$. The language under consideration is

$L_A^f = \Big\{ a \in A ~~:~~ \#\{ w \mid M(a,w) = 1 \} \geq f(|a|) \Big\}$.

In English, $L_A^f$ consists of, for each $n$, the members of $A$ of size $n$ that have at least $f(n)$ witnesses relative to $M$.

Some preliminary observations:

  1. $L_A^1 = A$ no matter what verifier you use.
  2. For any $A$ in NP with verifier $M$, you can make a verifier $M'$ for $A$ such that $L_A^f = A$. Just have $M'$ accept every witness $w$ that is accepted by $M$, plus $f(n)$ padded versions of the witness as well. Then $a \in A$ if and only if it has at least $f(n)$ witnesses relative to $M'$. This shows that if you aren't careful about first fixing the verifier, you can get trivial answers.

Some example questions/directions:

  1. What can we say about "parsimonious" or "minimal" verifiers? For instance, is there an NP-Complete language $A$ and verifier $M$ where $L_A^f$ becomes, say, not NP-Complete, or even trivial or empty, for some small $f$? What about $L_A^2$ (the members of $A$ with at least two witnesses)?

  2. On the other hand what about succinctly-represented families of solutions? Could we have $f = \omega(p(n))$ for all polynomials $p$, and some "reasonable" or "natural" verifier for an NP-Complete language $A$, and yet $L_A^f$ is in NP? (Meaning that the fact that a given $a \in A$ has superpolynomially many witnesses is provable without listing all the witnesses.)

  3. Anything about the above for a specific language $A$ such as SAT would be interesting.

Possibly (slightly) related: Does "Second-X is NP-Complete" Imply "X is NP-Complete"?

  • $\begingroup$ For 1, check complexity classes UP and FewP. $\endgroup$ – Tsuyoshi Ito Nov 24 '14 at 21:41
  • 1
    $\begingroup$ @TsuyoshiIto, thanks, those are good special cases. $\endgroup$ – usul Nov 25 '14 at 1:17

Your Answer


Browse other questions tagged or ask your own question.