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.

  • $\begingroup$ 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? $\endgroup$
    – Raphael
    Apr 23 '14 at 14:34
  • $\begingroup$ Yes, I was meaning NP complete or NP hard, or whatever that is not in P... Sorry and thanks to point out $\endgroup$
    – Marco
    Apr 23 '14 at 20:59
  • $\begingroup$ We don't know if NP-complete problems are not in P... $\endgroup$
    – 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.

  • 2
    $\begingroup$ 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.) $\endgroup$
    – David Eppstein
    Apr 23 '14 at 3:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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