11
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ The definition of "unique solution" is problematic: solving Parity games, for instance, is in UP (UP$\cap $coUP, in fact), but there may be many winning strategies. The unique witness is more involved. $\endgroup$ – Shaull Nov 11 '13 at 14:57
  • $\begingroup$ 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)? $\endgroup$ – valya Nov 11 '13 at 15:04
  • 7
    $\begingroup$ 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. $\endgroup$ – Shaull Nov 11 '13 at 15:14
  • $\begingroup$ 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! $\endgroup$ – Vincent Jan 23 '16 at 13:49
  • $\begingroup$ Btw your question from your last comment has since be answered on the Wikipedia page for the UP class $\endgroup$ – Vincent Jan 23 '16 at 13:50
12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Turbo Nov 19 '13 at 8:49
  • 1
    $\begingroup$ 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. $\endgroup$ – David Eppstein Nov 19 '13 at 16:18
  • $\begingroup$ This answer is absolutely brilliant as it teaches us even more than is asked for! $\endgroup$ – Vincent Jan 23 '16 at 13:51
11
$\begingroup$

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

$\endgroup$

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.