Re: Discussion about transformation TSP to UniqueTSP

In article <ekeke3$3t7$1@xxxxxxxxxxxxxxxxxxxxxxx>,
Rados³aw Hofman <radekh@xxxxxxxxx> wrote:
- there was discussion is UP class of problems or problem instances. For
example there are many SAT instances which has single accepting paths, but
there are also instances having many solutions - so is SAT in UP or outside
UP?

UP is a complexity class, so it is not a set of problem instances, but a set
of problems (or perhaps more precisely, a set of *languages*).

Whether SAT is in UP is an open question.

- UP?=NP - I think not - even if above problem was solved. I think that UP
would have been then like NP-complete - in NP and every problem from NP
could have been transformed to UP but it does not imply that UP=NP.

To avoid confusion, perhaps you should introduce a new complexity class
(HUP, for Hofman's UP?), define it precisely, and say what kinds of
transformations you're talking about. What you're saying about UP doesn't
jibe with the standard definition.

What is HUP---a set of decision problems (yes/no answer) or a set of
function problems ("find the optimal solution")? What kinds of reductions
do you allow---many-to-one (Karp) reductions only (where you have to
transform the input of one problem to the input of another problem) or
also Turing reductions (where you can use an oracle for one problem to
help solve another one)?
--
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
.