Re: Discussion about transformation TSP to UniqueTSP

In article <1164699419.202495.242710@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Radoslaw Hofman <radekh@xxxxxxxxx> wrote:
Maybe I know too little about UP but I think it can be considered in
two ways. It depends if we assume that uniqueness of solution is
property of language or instance. For example let us consider language:
1. "X is graduate from PUT"
- X may be one of thousands
2. "X is graduate from PUT born on DD.MM.YYYY"
- depending on date X may be unique or not
3. "X is graduate from PUT with SSID=YYYY"
- this always has unique solution

Is second sentence in UP?

Let me address what I think is your concern, not by answering your question
directly (which I find somewhat vague), but by using an actual example of a
language that is in UP. Consider the following language:

FACTOR = {(m,r) | There exists s such that 1<s<r and s divides m}

FACTOR is a set of ordered pairs of positive integers, and it is clearly
in NP, because there is a simple "guess-and-check" algorithm for it.
Namely, guess s and check to see if it divides m.

It turns out that FACTOR is also in UP, but proving this takes a little
more cleverness than exhibiting the above algorithm. To show that FACTOR
is in UP, we need to show that there is a guess-and-check algorithm for
it with the property that, for members x of FACTOR, there is a *unique*
guess that works. The problem with the above algorithm is that m might
have many different factors in the specified range, in which case there
will be multiple guesses that work.

The trick is to use the so-called "fundamental theorem of arithmetic,"
which says that integers have a unique prime factorization. So we can
do the following: guess the prime factorization of m, check that the
alleged prime factorization is indeed a prime factorization (this can
be done in polynomial time, either by using primality certificates or
by using Agrawal et al.'s polynomial-time primality testing algorithm),
and then use the prime factorization to check if there exists an s with
the desired properties.

This algorithm forces us to get the correct prime factorization of m
first, before we look for a candidate s. While this might seem like a
strange thing to do, it achieves the goal of ensuring that only *one*
nondeterministic path through the machine accepts any given element
of FACTOR, and therefore shows that FACTOR is in UP.

So, depending on what you mean by a "solution," there may be a unique
"solution" or there may be multiple "solutions." This ambiguity does
not, however, mean that the definition of UP is ambiguous, nor does it
mean that the question of whether FACTOR is in UP is ambiguous.

It's partly to avoid ambiguities like this that complexity theory tends
to focus on *languages* and their membership in complexity classes,
rather than on "problems" and "solutions." The terminology of problems
and solutions is more natural for a practitioner, but for theoretical
purposes the terminology of languages is usually more precise.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.

Relevant Pages

  • P Versus NP
    ... determine whether every language accepted by some nondeterministic ... algorithm in polynomial time is also accepted by some ... L = Lfor some Turing machine M which runs in polynomial time} The ... We say that R is polynomial-time iff L R ...
    (sci.math)
  • Re: Mr. P and Ms. S
    ... determine whether every language accepted by some nondeterministic ... algorithm in polynomial time is also accepted by some ... L = Lfor some Turing machine M which runs in polynomial time} The ... We say that R is polynomial-time iff L R ...
    (sci.math)
  • P6 = NP (WAS: an oracle paradox)
    ... theory is the Turing machine,introduced by Alan Turing in 1936 ... solvable by some algorithm within anumber of steps bounded by some xed ... over .Then a language over is a subset L of. ... We say that R is polynomial-time i LR ...
    (sci.math)
  • Re: pseudo code v/s algorithm
    ... insert your language here) than code. ... There is absolutely no difference between algorithm and code, ... If I have an implementation or pseudo-code it cannot be ... Turing Machine or lambda-calculus in it, modulo the infinite memory ...
    (comp.programming)
  • Re: pseudo code v/s algorithm
    ... insert your language here) than code. ... There is absolutely no difference between algorithm and code, ... If I have an implementation or pseudo-code it cannot be ... just have a look at the sources of some Common Lisp ...
    (comp.programming)