Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

migrated from Apr 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

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.