<p>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$).</p>

CC BY-SA 3.0
2014-07-16T13:46:17.183Z
This is exactly what I was looking for. Cheers!
gdiazc
CC BY-SA 3.0
2014-07-16T13:51:34.960Z
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
CC BY-SA 3.0
2014-07-16T16:31:54.270Z
@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
CC BY-SA 3.0
2014-07-16T17:20:39.317Z
@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: http://dx.doi.org/10.1007/BFb0028987
Joshua Grochow
CC BY-SA 3.0
2014-07-23T15:20:17.867Z
@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
CC BY-SA 3.0
2014-07-16T13:17:19.310Z
2014-07-16T13:32:43.550Z
2014-07-16T13:32:43.550Z
Mohammad Al-Turkistany
<p>Let's call a language $L \in$ NP <em>sparsely certificated</em> if and only if:</p>

<p>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)$.</p>

<p>In shorter terms, every input $x$ has at a most polynomial amount of certificates which verify its inclusion in $L$.</p>

<p><strong>Example:</strong> To illustrate, consider the $\mathbf{CLIQUE}$ problem:</p>

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

<p>The language $\mathbf{CLIQUE}$ is <strong>not</strong> <em>sparsely certificated</em>, 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}$.</p>

<p><strong>End Example</strong></p>

<p>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!</p>

<p><strong>Note</strong>: this definition is different from that of a sparse language!</p>

CC BY-SA 3.0
2014-07-16T15:50:44.443Z
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
<cc.complexity-theory><complexity-classes>
NP-complete problem with polynomially many certificates?
gdiazc
# NP-complete problem with polynomially many certificates?

(Asked by: username_0 on 2014-07-16)

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!

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2014-07-16. Score: 12 | Accepted answer

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$).

> **Comments:**
> **username_0**: This is exactly what I was looking for. Cheers!  
> **username_0**: 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?  
> **username_3**: @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}$.  
> **username_3**: @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: http://dx.doi.org/10.1007/BFb0028987  
> **username_4**: @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"....  

---

