NP-problema completo com polinomialmente muitos certificados?

Vamos chamar um idioma NP com pouca certificação se e somente se:$L \in$

Existe um polinómio de tal modo que para cada entrada x ∈ Σ * de tamanho n , se x ∈ L , em seguida, o conjunto de L x de certificados u que verificam se x ∈ L é polinomialmente dimensionada, isto é, | L x | ≤ p ( n ) .$p : \mathbb{N} \rightarrow \mathbb{N}$$x \in \Sigma^*$$n$$x \in L$$U_x$$u$$x \in L$$|U_x| \leq p(n)$

Em termos mais curtos, cada entrada possui, numa quantidade mais polinomial de certificados que verificam a sua inclusão em L .$x$$L$

Exemplo: Para ilustrar, considere o problema :$\mathbf{CLIQUE}$

$\mathbf{CLIQUE} = \{\; (G,k) \;\mid\; G \text{ has a clique of size } k \;\}$

A linguagem é não escassamente certificado , como uma entrada x = ( L , k ) pode facilmente ter uma quantidade exponencial de k -cliques actuam como certificados que provam que x ∈ C G I Q L E .$\mathbf{CLIQUE}$ $x = (G,k)$$k$$x \in \mathbf{CLIQUE}$

Exemplo final

A questão, então, é: existe alguma linguagem com certificação NP completa e esparsamente certificada? Quaisquer informações são bem-vindas, mesmo que não respondam à pergunta!

Nota : esta definição é diferente da de uma linguagem esparsa!

$NP$$fewP$$fewP \ne NP$$NP$$fewP=NP$