Problèmes NP avec une solution unique

8

Y a-t-il une classe de problèmes NP qui ont une solution unique? C'est ce que je demande, parce que lorsque j'étudiais la cryptographie, j'ai lu sur le sac à dos et j'ai trouvé l'idée très intéressante.

complexity-theory decision-problem np cryptography Marco
la source
Vous semblez hésiter sur votre terminologie; Les problèmes NP peuvent être arbitrairement faciles, et ce sont généralement des problèmes de décision (qui ont toujours une solution unique, oui ou non); en savoir plus sur nos questions de référence . Je suppose que vous voulez des problèmes NPO-hard avec des solutions uniques?
Raphael
Oui, je voulais dire NP complet ou NP dur, ou tout ce qui n'est pas en P ... Désolé et merci de le signaler
Marco
Nous ne savons pas si les problèmes NP-complets ne sont pas en P ...
Raphael

Réponses:

12

Oui, la classe est appelée UP (le U signifie "sans ambiguïté"). David souligne dans les commentaires qu'une autre réponse est américaine .

UP: Si X∈L, alors il y a exactement une "preuve" ("témoin", "certificat", "chemin d'acceptation"). SiX∉L, il n'y a exactement aucune "preuve".

NOUS: Si X∈L, alors il y a exactement une "preuve". SiX∉L, il peut y avoir zéro preuve, ou 2+ preuves, tant qu'il n'y en a pas exactement une.

usul
la source
2
Ou aux États-Unis, une classe de complexité différente. (Pour les machines UP, il y a toujours au plus un chemin d'acceptation, pour les États-Unis, il peut y en avoir plus d'un mais ils n'acceptent que s'il y en a exactement un.)