Take the 2-minute tour ×
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.

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|improve this question

migrated from mathoverflow.net Apr 23 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 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 at 20:59
    
We don't know if NP-complete problems are not in P... –  Raphael Apr 23 at 21:06

1 Answer 1

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|improve this answer
2  
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 at 3:34

Your Answer

 
discard

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.