Let's call a language $L \in$ NP sparsely certificated if and only if:There exists a polynomial $p : \mathbb{N} \rightarrow \mathbb{N}$ such that for every input $x \in \Sigma^*$ of size $n$, if $x \in L$ then the set $U_x$ of certificates $u$ which verify that $x \in L$ is polynomially sized, i.e. $|U_x| \leq p(n)$.In shorter terms, every input $x$ has at a most polynomial amount of certificates which verify its inclusion in $L$.Example: To illustrate, consider the $\mathbf{CLIQUE}$ problem:$\mathbf{CLIQUE} = \{\; (G,k) \;\mid\; G \text{ has a clique of size } k \;\}$The language $\mathbf{CLIQUE}$ is not sparsely certificated, as an input $x = (G,k)$ could easily have an exponential amount of $k$-cliques acting as certificates which prove that $x \in \mathbf{CLIQUE}$.End ExampleThe question, then, is: are there any known NP-complete sparsely certificated languages? Any insights are welcome, even if they don't answer the question!Note: this definition is different from that of a sparse language!
NP-complete problem with polynomially many certificates?
cc.complexity theory;complexity classes
No, there is no known sparsely certified $NP$-complete languages. The class that you are describing is known as $fewP$. It is widely believed that $fewP \ne NP$, So, No $NP$-complete problem is known to be in fewP. (It is impossible unless $fewP=NP$).