# NP Problems with unique solution

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.

## migrated from mathoverflow.netApr 23 '14 at 10:38

This question came from our site for professional mathematicians.

• You seem to be shaky on your terminology; NP problems can be arbitrarily easy, and they are usually decision problems (which always have a unique solution, yes or no); read more at our reference questions. I assume you want NPO-hard problems with unique solutions? – Raphael Apr 23 '14 at 14:34
• Yes, I was meaning NP complete or NP hard, or whatever that is not in P... Sorry and thanks to point out – Marco Apr 23 '14 at 20:59
• We don't know if NP-complete problems are not in P... – Raphael Apr 23 '14 at 21:06

## 1 Answer

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.

• Or US, a different complexity class. (For UP machines, there is always at most one accepting path, for US there can be more than one but they only accept if there is exactly one.) – David Eppstein Apr 23 '14 at 3:34