# NP-complete problem with polynomially many certificates?

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 Example

The 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!

• To be sure I understand, is this correct? $U_x$ is technically defined with respect to some particular verifier $V$, that is, for $x \in L$, $U_x = \{u : V(x,u) = 1\}$. And $L$ is "sparsely certificated" if and only if there exists a verifier $V$ for $L$ such that its $U_x$s satisfy the polynomial-size condition. – usul Jul 16 '14 at 15:50

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$).
• I have found references for fewP (at the Complexity Zoo), but would you happen to have a reference to support the statement: "it is widely believed that fewP $\neq$ NP"? For example, would fewP $=$ NP imply $P = NP$ or something of the sort? – gdiazc Jul 16 '14 at 13:51
• @TayfunPay: I'm pretty sure he's talking about $\mathsf{FewP}$ and not $\mathsf{Few}$. $\mathsf{Few}$ is more general - it requires at most polynomially certificates be accepted by the verifier, but whether $x \in L$ or not is not determined by whether there exist a certificate accepted by the verifier, but rather an additional predicate $Q(x, |U_x|)$. The OQ seems to be intending to ask about where the existence of any certificate implies $x \in L$, which is exactly $\mathsf{FewP}$. – Joshua Grochow Jul 16 '14 at 16:31
• @TayfunPay: As far as I understand it, $\mathsf{Few}$ and $\mathsf{FewP}$ are both semantic classes, just like $\mathsf{UP}$ or $\mathsf{BPP}$. In particular, what you say is incorrect. $\mathsf{Few}$, just like $\mathsf{FewP}$, requires that the number of accepting paths of the verifier is bounded by a polynomial on all inputs. (What you defined is something like $\mathsf{PromiseFew}$ or $\mathsf{PromiseFewP}$...) See Def. 1.2 of Cai & Hemachandra: dx.doi.org/10.1007/BFb0028987 – Joshua Grochow Jul 16 '14 at 17:20
• @JoshuaGrochow I just got a chance to look over it. You are correct, ${\bf Few}$ is indeed a semantic class. I thought that it was the syntactic version of ${\bf FewP}$. OK However, I still believe the questionnaire was asking for "if and only if" type of a scenario. Because a given language $L$ is in ${\bf FewP}$ "if" the total number of accepting paths are bounded by a polynomial and "not" in ${\bf FewP}$ if the there are no accepting paths. Thus we do NOT know what happens when the number of accepting paths are exponential because it is not "if and only if".... – Tayfun Pay Jul 23 '14 at 15:20