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$
$\endgroup$
3
-
$\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$– RaphaelCommented Apr 23, 2014 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$– MarcoCommented Apr 23, 2014 at 20:59
-
$\begingroup$ We don't know if NP-complete problems are not in P... $\endgroup$– RaphaelCommented Apr 23, 2014 at 21:06
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
-
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 EppsteinCommented Apr 23, 2014 at 3:34