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:$L_A^1 = A$ no matter what verifier you use.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: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)?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.)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?
Properties of second-order NP (complete) languages
cc.complexity theory;np;np complete