10
$\begingroup$

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!

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – usul
    Jul 16 '14 at 15:50
12
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ This is exactly what I was looking for. Cheers! $\endgroup$
    – gdiazc
    Jul 16 '14 at 13:46
  • $\begingroup$ 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? $\endgroup$
    – gdiazc
    Jul 16 '14 at 13:51
  • 1
    $\begingroup$ @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}$. $\endgroup$
    – Joshua Grochow
    Jul 16 '14 at 16:31
  • 1
    $\begingroup$ @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 $\endgroup$
    – Joshua Grochow
    Jul 16 '14 at 17:20
  • $\begingroup$ @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".... $\endgroup$
    – Tayfun Pay
    Jul 23 '14 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.