NP Probleme mit einzigartiger Lösung

8

Gibt es eine Klasse von NP-Problemen, die eine einzige Lösung haben? Ich frage das, denn als ich Kryptographie studierte, las ich über den Rucksack und fand die Idee sehr interessant.

complexity-theory decision-problem np cryptography Marco
quelle
Sie scheinen in Ihrer Terminologie wackelig zu sein; NP-Probleme können beliebig einfach sein und sind normalerweise Entscheidungsprobleme (die immer eine eindeutige Lösung haben, ja oder nein). Lesen Sie mehr bei unseren Referenzfragen . Ich nehme an, Sie wollen NPO-harte Probleme mit einzigartigen Lösungen?
Raphael
Ja, ich meinte NP komplett oder NP hart, oder was auch immer das nicht in P ist ... Entschuldigung und danke darauf hinzuweisen
Marco
Wir wissen nicht, ob NP-vollständige Probleme nicht in P ...
Raphael

Antworten:

12

Ja, die Klasse heißt UP (das U steht für "eindeutig"). David weist in den Kommentaren darauf hin, dass eine andere Antwort US ist .

x∈Lx∉L

x∈Lx∉L

usul
quelle
2
Oder USA, eine andere Komplexitätsklasse. (Für UP-Maschinen gibt es immer höchstens einen akzeptierenden Pfad, für die USA kann es mehr als einen geben, aber sie akzeptieren nur, wenn es genau einen gibt.)