<p>I agree with Shaull's comment that the intuition of having a unique witness is correct, but subtle. The argument in your last paragraph can be made technically precise, and highlights the subtlety of $\mathsf{UP}$ versus $\mathsf{NP}$. In particular, the problem in your last paragraph is essentially the question of whether $\mathsf{NPMV} \subseteq_{c} \mathsf{NPSV}$:</p>

<p>$\mathsf{NPMV}$ is the class of partial multi-valued functions computable in non-deterministic polynomial time, that is, each accepting nondeterministic branch gets to output a value (if there are no accepting paths on some input, then there is no output, leading to the fact that these need only be <em>partial</em> functions). This is closely related to the search version of $\mathsf{NP}$ problems.</p>

<p>$\mathsf{NPSV}$ is the class of <em>single</em>-valued functions in $\mathsf{NPMV}$, that is, multiple branches can accept, but if any branches do accept, all of the accepting branches must output the same value.</p>

<p>Intuitively, your last paragraph is talking about whether or not you can always select, from among the witnesses for a given verifier of some $\mathsf{NP}$ problem, a single witness. This is the question of whether every $\mathsf{NPMV}$ function has an $\mathsf{NPSV}$ refinement (denoted $\mathsf{NPMV} \subseteq_{c} \mathsf{NPSV}$). If this is the case, then the polynomial hierarchy collapses (see <a href="http://dx.doi.org/10.1137/S0097539794268315" rel="nofollow">Hemaspaandra, Naik, Ogihara, and Selman "Computing Solutions Uniquely Collapses the Polynomial Hierarchy"</a>). </p>

<p>To contrast with $\mathsf{UP}$, no such implication is known to follow from $\mathsf{NP} = \mathsf{UP}$. Essentially because given a language $L \in \mathsf{NP}$, the (witnesses for a) $\mathsf{UP}$ machine for $L$ need not have anything to do with (the witnesses for any) other $\mathsf{NP}$ machine(s) for $L$.</p>

CC BY-SA 3.0
2013-11-12T16:44:04.707Z
2013-11-17T15:56:51.560Z
2013-11-17T15:56:51.560Z
Joshua Grochow
<p>Your confusion appears to be over the fact that $\mathsf{NP}$ problems have more than one way to define a "solution" (or witness). The type of the solution is not part of the definition of the problem. For instance, for graph coloring, the obvious type of solution is an assignment of one color for each vertex (using at most the required number of colors); however, by the <a href="https://en.wikipedia.org/wiki/Gallai%E2%80%93Hasse%E2%80%93Roy%E2%80%93Vitaver_theorem">Gallai–Hasse–Roy–Vitaver theorem</a> another type of solution that works equally well is an assignment of an orientation to each edge (creating directed paths of at most the required number of vertices). These two types of solutions can both be checked in polynomial time, but by different algorithms, and they also have different combinatorial properties. For instance, for a typical problem instance, the number of vertex color assignments will be different from the number of edge orientations. A lot of research on speeding up exponential algorithms for NP type problems can be interpreted as finding a new family of solutions to the same problem that has fewer possibilities to check.</p>

<p>Every problem in $\mathsf{P}$ has an $\mathsf{NP}$ "solution" consisting only of the empty string. To verify that this is a solution, just check that the solution string is empty and then run the polynomial time algorithm for the problem instance. With this type of solution, every yes instance has exactly one valid solution and every no instance has zero, meeting the definition of $\mathsf{UP}$ and showing that $\mathsf{P}\subset\mathsf{UP}$. If $\mathsf{P}=\mathsf{NP}$ then the same empty-string solution would also work for every problem in $\mathsf{NP}$, showing that $\mathsf{NP}=\mathsf{UP}$. So there is no contradiction between the fact that the empty-string solution is unique and the fact that some other type of solution for the same problem is non-unique.</p>

CC BY-SA 3.0
2013-11-19T08:49:27.943Z
So the implication $UP=NP$ is not contradictory? The following problem is NP-complete. Given N is there a factor of N in a given range $[a,b]$ say where $a,b\sim N^{\frac{1}{4}}$ and $a<b$? There could be more than one factor in that range and the solution may not be unique?
Turbo
CC BY-SA 3.0
2013-11-19T16:18:31.950Z
Again, you are assuming incorrectly that the solution can only be the factor you are looking for. There may be other ways of solving the same problem (i.e. of getting a yes or no answer for the given N) that do not consist of a factor. And if P=NP the empty string meets the technical requirements of an NP solution — you can check it in polynomial time — and is indeed not a factor but is a solution to the same problem.
David Eppstein
CC BY-SA 3.0
2016-01-23T13:51:21.403Z
This answer is absolutely brilliant as it teaches us even more than is asked for!
Vincent
CC BY-SA 3.0
2013-11-17T22:17:02.217Z
2013-11-19T00:59:38.107Z
2013-11-19T00:59:38.107Z
David Eppstein
<p>UP class is <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aU#up">defined</a> as such:</p>

<blockquote>
  <p>The class of decision problems solvable by an NP machine such that</p>
  
  <p>If the answer is 'yes,' exactly one computation path accepts.</p>
  
  <p>If the answer is 'no,' all computation paths reject.</p>
</blockquote>

<p>I'm trying to develop intuition for this definition.</p>

<p>Can one say that UP problems are the problems with unique solutions (e.g. prime factorisation)?</p>

<p>That seems close to the truth to me; but I can't help thinking that that would mean, since UP contains P and is contained in NP, that in case <code>P = NP</code> we'd get that <code>P = UP = NP</code>, so all problems in <code>NP</code> have unique solutions as well, which seems like something provably not true: <code>P != NP</code> by reductio ad absurdum. I hope there's not too much conjectures and hand-wavery in this paragraph for your taste.</p>

CC BY-SA 3.0
2013-11-11T14:57:19.633Z
The definition of "unique solution" is problematic: solving [Parity games](http://en.wikipedia.org/wiki/Parity_game), for instance, is in UP (UP$\cap $coUP, in fact), but there may be many winning strategies. The unique witness is more involved.
Shaull
CC BY-SA 3.0
2013-11-11T15:04:15.283Z
hm, so that would mean there's an algorithm for a non-deterministic Turing machine, which is not "non-deterministically try every solution" (I thought that's the idea in the heart of the equivalence of definitions of NP for n.-d. and d. T.m.), but something more sophisticated, always leading to the unique result out of many possible... Is that right? Is there another way to state it, for example using only the idea of a deterministic T.m. (one can define NP using only it)?
valya
CC BY-SA 3.0
2013-11-11T15:14:24.960Z
The intuition of unique witness is correct, but must be used carefully, since it doesn't mean that *every* NTM for it has a unique run.
Shaull
CC BY-SA 3.0
2016-01-23T13:49:26.890Z
I love this question! I had the exact same confusion but I didn't see the clever way to translate this confusion into a simple proof that P != NP. Well done!
Vincent
CC BY-SA 3.0
2016-01-23T13:50:01.623Z
Btw your question from your last comment has since be answered on the Wikipedia page for the UP class
Vincent
<cc.complexity-theory><complexity-classes>
Intuition for the UP class
valya
# Intuition for the UP class

(Asked by: username_0 on 2013-11-11)

UP class is [defined](https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aU#up) as such:

> The class of decision problems solvable by an NP machine such that
>
> If the answer is 'yes,' exactly one computation path accepts.
>
> If the answer is 'no,' all computation paths reject.

I'm trying to develop intuition for this definition.

Can one say that UP problems are the problems with unique solutions (e.g. prime factorisation)?

That seems close to the truth to me; but I can't help thinking that that would mean, since UP contains P and is contained in NP, that in case `P = NP` we'd get that `P = UP = NP`, so all problems in `NP` have unique solutions as well, which seems like something provably not true: `P != NP` by reductio ad absurdum. I hope there's not too much conjectures and hand-wavery in this paragraph for your taste.

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: The definition of "unique solution" is problematic: solving [Parity games](http://en.wikipedia.org/wiki/Parity_game), for instance, is in UP (UP$\cap $coUP, in fact), but there may be many winning strategies. The unique witness is more involved.  
> **username_0**: hm, so that would mean there's an algorithm for a non-deterministic Turing machine, which is not "non-deterministically try every solution" (I thought that's the idea in the heart of the equivalence of definitions of NP for n.-d. and d. T.m.), but something more sophisticated, always leading to the unique result out of many possible... Is that right? Is there another way to state it, for example using only the idea of a deterministic T.m. (one can define NP using only it)?  
> **username_1**: The intuition of unique witness is correct, but must be used carefully, since it doesn't mean that *every* NTM for it has a unique run.  
> **username_2**: I love this question! I had the exact same confusion but I didn't see the clever way to translate this confusion into a simple proof that P != NP. Well done!  
> **username_2**: Btw your question from your last comment has since be answered on the Wikipedia page for the UP class  

---

## 2 answers

### Answer by username_4 on 2013-11-17. Score: 13 | Accepted answer

Your confusion appears to be over the fact that $\mathsf{NP}$ problems have more than one way to define a "solution" (or witness). The type of the solution is not part of the definition of the problem. For instance, for graph coloring, the obvious type of solution is an assignment of one color for each vertex (using at most the required number of colors); however, by the [Gallai–Hasse–Roy–Vitaver theorem](https://en.wikipedia.org/wiki/Gallai%E2%80%93Hasse%E2%80%93Roy%E2%80%93Vitaver_theorem) another type of solution that works equally well is an assignment of an orientation to each edge (creating directed paths of at most the required number of vertices). These two types of solutions can both be checked in polynomial time, but by different algorithms, and they also have different combinatorial properties. For instance, for a typical problem instance, the number of vertex color assignments will be different from the number of edge orientations. A lot of research on speeding up exponential algorithms for NP type problems can be interpreted as finding a new family of solutions to the same problem that has fewer possibilities to check.

Every problem in $\mathsf{P}$ has an $\mathsf{NP}$ "solution" consisting only of the empty string. To verify that this is a solution, just check that the solution string is empty and then run the polynomial time algorithm for the problem instance. With this type of solution, every yes instance has exactly one valid solution and every no instance has zero, meeting the definition of $\mathsf{UP}$ and showing that $\mathsf{P}\subset\mathsf{UP}$. If $\mathsf{P}=\mathsf{NP}$ then the same empty-string solution would also work for every problem in $\mathsf{NP}$, showing that $\mathsf{NP}=\mathsf{UP}$. So there is no contradiction between the fact that the empty-string solution is unique and the fact that some other type of solution for the same problem is non-unique.

> **Comments:**
> **username_5**: So the implication $UP=NP$ is not contradictory? The following problem is NP-complete. Given N is there a factor of N in a given range $[a,b]$ say where $a,b\sim N^{\frac{1}{4}}$ and $a<b$? There could be more than one factor in that range and the solution may not be unique?  
> **username_4**: Again, you are assuming incorrectly that the solution can only be the factor you are looking for. There may be other ways of solving the same problem (i.e. of getting a yes or no answer for the given N) that do not consist of a factor. And if P=NP the empty string meets the technical requirements of an NP solution — you can check it in polynomial time — and is indeed not a factor but is a solution to the same problem.  
> **username_2**: This answer is absolutely brilliant as it teaches us even more than is asked for!  

---

### Answer by username_3 on 2013-11-12. Score: 11

I agree with Shaull's comment that the intuition of having a unique witness is correct, but subtle. The argument in your last paragraph can be made technically precise, and highlights the subtlety of $\mathsf{UP}$ versus $\mathsf{NP}$. In particular, the problem in your last paragraph is essentially the question of whether $\mathsf{NPMV} \subseteq\_{c} \mathsf{NPSV}$:

$\mathsf{NPMV}$ is the class of partial multi-valued functions computable in non-deterministic polynomial time, that is, each accepting nondeterministic branch gets to output a value (if there are no accepting paths on some input, then there is no output, leading to the fact that these need only be *partial* functions). This is closely related to the search version of $\mathsf{NP}$ problems.

$\mathsf{NPSV}$ is the class of *single*-valued functions in $\mathsf{NPMV}$, that is, multiple branches can accept, but if any branches do accept, all of the accepting branches must output the same value.

Intuitively, your last paragraph is talking about whether or not you can always select, from among the witnesses for a given verifier of some $\mathsf{NP}$ problem, a single witness. This is the question of whether every $\mathsf{NPMV}$ function has an $\mathsf{NPSV}$ refinement (denoted $\mathsf{NPMV} \subseteq\_{c} \mathsf{NPSV}$). If this is the case, then the polynomial hierarchy collapses (see [Hemaspaandra, Naik, Ogihara, and Selman "Computing Solutions Uniquely Collapses the Polynomial Hierarchy"](http://dx.doi.org/10.1137/S0097539794268315)).

To contrast with $\mathsf{UP}$, no such implication is known to follow from $\mathsf{NP} = \mathsf{UP}$. Essentially because given a language $L \in \mathsf{NP}$, the (witnesses for a) $\mathsf{UP}$ machine for $L$ need not have anything to do with (the witnesses for any) other $\mathsf{NP}$ machine(s) for $L$.


---

