Problème NP-complet avec de nombreux certificats polynomiaux?

10

Appelons une langue NP peu certifiée si et seulement si:L

Il existe un polynôme tel que pour chaque entrée x Σ de taille n , si x L alors l'ensemble U x des certificats u qui vérifient que x L est de taille polynomiale, ie | U x | p ( n ) .p:NNxΣnxLUxuxL|Ux|p(n)

En termes plus courts, chaque entrée est à une quantité plus polynomiale des certificats qui vérifient son inclusion dans L .xL

Exemple: Pour illustrer, considérons le problème :CLIQUE

CLIQUE={(G,k)G has a clique of size k}

Le langage est pas peu certifiée , en entrée x = ( G , k ) peut facilement avoir une quantité exponentielle de k -cliques agissant comme des certificats qui prouvent que x C L I Q U E .CLIQUE x=(G,k)kxCLIQUE

Exemple de fin

La question est donc: existe-t-il des langues certifiées NP-complètes et peu certifiées? Toutes les informations sont les bienvenues, même si elles ne répondent pas à la question!

Remarque : cette définition est différente de celle d'une langue clairsemée!

gdiazc
la source
Pour être sûr de bien comprendre, est-ce correct? est techniquement défini par rapport à un vérificateur particulier V , c'est-à-dire que pour x L , U x = { u : V ( x , u ) = 1 } . Et L est "faiblement certifié" si et seulement s'il existe un vérificateur V pour L tel que ses U x s satisfassent à la condition de taille polynomiale. UxVxLUx={u:V(x,u)=1}LVLUx
usul

Réponses:

12

Non, il n'y a pas de langues complètes et certifiées . La classe que vous décrivez est connu sous le nom f e w P . On croit généralement que f e w P N P , donc, Non N P problème -complete est connu pour être en fewP. (C'est impossible à moins que f e w P = N P ).NPfewPfewPNPNPfewP=NP

Mohammad Al-Turkistany
la source
Ceci est exactement ce que je cherchais. À votre santé!
gdiazc
J'ai trouvé des références pour fewP (au Complexity Zoo), mais auriez-vous une référence pour soutenir la déclaration: "il est largement admis que fewP NP"? Par exemple, est-ce que peu P = NP impliquerait P = N P ou quelque chose du genre? =P=NP
gdiazc
1
FewPFewFewxLQ(x,|Ux|)xLFewP
1
FewFewPUPBPPFewFewPPromiseFewPromiseFewP
FewFewPLFewPFewP
Tayfun Pay