Intuition for the UP class

Question

UP class is defined 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.

Answer 1

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 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.

Answer 2

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").

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$.