Appelons une langue NP peu certifiée si et seulement si:
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 ) .
En termes plus courts, chaque entrée est à une quantité plus polynomiale des certificats qui vérifient son inclusion dans L .
Exemple: Pour illustrer, considérons le problème :
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 .
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!
Réponses:
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 ).NP fewP fewP≠NP NP fewP=NP
la source