patternModerate
NP Problems with unique solution
Viewed 0 times
withuniqueproblemssolution
Problem
Is there any class of NP problems that have one unique solution?
I'm asking that, because when I was studying cryptography I read about the knapsack and I found very interesting the idea.
I'm asking that, because when I was studying cryptography I read about the knapsack and I found very interesting the idea.
Solution
Yes, the class is called UP (the U standing for "unambiguous"). David points out in the comments that another answer is US.
UP: If $x \in L$, then there is exactly one "proof" ("witness", "certificate", "accepting path"). If $x \not\in L$, there are exactly zero "proofs".
US: If $x \in L$, then there is exactly one "proof". If $x \not\in L$, there may be zero proofs, or 2+ proofs, as long as there is not exactly one.
UP: If $x \in L$, then there is exactly one "proof" ("witness", "certificate", "accepting path"). If $x \not\in L$, there are exactly zero "proofs".
US: If $x \in L$, then there is exactly one "proof". If $x \not\in L$, there may be zero proofs, or 2+ proofs, as long as there is not exactly one.
Context
StackExchange Computer Science Q#24043, answer score: 12
Revisions (0)
No revisions yet.