Discussion about transformation TSP to UniqueTSP

Hi,



My usenet client is fed up with depth of discussion about Mr. Diaby TSP
conjecture where algorithm converting TSP to UniqueTSP appeared. Idea was
simple - we shift all weights by large number and add some value to each
weight ensuring that there will be only one optimal solution. I then propose
to continue discussion about H&D algorithm here.



I have proposed N^2 bites shift (adding "extra space"), while there was
discussion "can it be less". In mine opinion minimal shift needs N^log(N) -
we have to separate each number in such way that after adding them we can be
sure that we can distinct what was taken to sum. Following example of
implementation in mine opinion has error in step 3 - if we add same value to
all arcs from city i then in overall cost we will be unable to recognize
sequence used - every sum will contain N x 1 in extra space.



Answering some of doubts discussed previously:



- usage of this transformation for heuristics - I don't feel like it changes
something... For large instances we will have only one unique optimal TSP
tour... but difference to some non-optimal tours may be less then
0.000000001% so heuristics will consider them too



- decision version - each NP-complete problem can be transformed to Hamilton
Cycle problem which can be converted to TSP with question "Is there TSP tour
with overall Cost <=N" (in transformation we assign 1 to every arc existing
in HC instance and 100 for every arc added to obtain TSP instance) - this
makes decision version ask for optimal C, but after transformation we loose
this ability. My attempt to solve it via checking one by one N^2 problems is
incorrect - it will preserve correctness of solution, but it does not ensure
uniqueness of optimal assignment



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



Until/unless we will be able to find some use of this algorithm I feel
slight motivation to finish it up in terms of solid proves...



Best regards,



Radek Hofman




U¿ytkownik "deepakc" <deepakc{}pmail.ntu.edu.sg> napisa³ w wiadomo¶ci
news:1164536766.019077.199280{}j44g2000cwa.googleg roups.com...
> Dear Everyone,
>
> I was thinking along the lines that Mr/Ms Mathisart told me
> earlier...regarding how to optimize the H&D Algorithm.
>
> And now I have found a more optimized version of the H&D
> Algorithm,...we need to now go only upto 2^N and not upto 2^(N^2).
> Thank you Mathisart (is that ur real name by the way ?)
>
> Of course, both versions of Algorithms are polynomial in space & time,
> but still this one is better:
>
> BETTER VERSION OF HOFMAN & DEEPAK (H&D) ALGORITHM
> 1.) Multiply all the edges of the TSP with the same large constant
> C=(2^N) where N is the number of cities
> 2.) i=0
> 3.) Now add 2^i to all Edges coming out of City(i)
> 4.) i=i+1
> 5.) Loop to Step 3, until i=(N-1)..that means loop until all Cities
> have been covered
> 6.) Exit
>
> All the 8 Theorems that I mentioned in my previous post "280" also
> apply for the above Algorithm.
>
> -Deepak
>

Hay

U¿ytkownik "Rados³aw Hofman" <radekh{}teycom.pl> napisa³ w wiadomo¶ci
news:ekeke3$3t7$1{}sunflower.man.poznan.pl...
> I have proposed N^2 bites shift (adding "extra space"), while there was
> discussion "can it be less". In mine opinion minimal shift needs
> N^log(N) -

I meant N*log(N) bites

From each city we have N outgoing arcs - so we need log(N) bites to have
distinct signature for each, and because they have to be separated then each
city will have separate log(N) bites, so N*log(N).

Weigth is then multipied by 2^(N*log(N))

Best regards,

Radek Hofman

In article <ekeke3$3t7$1{}sunflower.man.poznan.pl>,
Rados³aw Hofman <radekh{}teycom.pl> 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

Rados³aw Hofman wrote:
> - decision version - each NP-complete problem can be transformed to Hamilton
> Cycle problem which can be converted to TSP with question "Is there TSP tour
> with overall Cost <=N" (in transformation we assign 1 to every arc existing
> in HC instance and 100 for every arc added to obtain TSP instance) - this
> makes decision version ask for optimal C, but after transformation we loose
> this ability. My attempt to solve it via checking one by one N^2 problemsis
> incorrect - it will preserve correctness of solution, but it does not ensure
> uniqueness of optimal assignment

I'm not entirely sold that this is true. You do know, trivially, that
N = N * multiplicitive cost + min(chose #_of_vertices - 1: of additive
costs). Where min satisfies 2^(1) + ... + 2^(number of vertices -1) <=
min <= 2^(number of edges) + ... + 2^((number of edges) - ((number of
vertices) -1)).

This reduces the options a lot, and I'd bet it still reduces quite a
bit further. For instance, you can limit the number of edges to 2 *
factorial(vertices) by reducing a general TSP so that only the cheapest
edge{a,b} is selected...

I think I read somewhere that a TSP with different costs for edge{a,b}
and edge{b,a} can be reduced to a (larger) TSP with edge{a,b} =
edge{b,a}. This limits the right side of the equality-relation in
min() to the factorial of the vertices.

A non-random distribution of additive costs might go a long way
further. ...anyway, I'm out of time right now.

mathisart wrote:
> Rados³aw Hofman wrote:
> I think I read somewhere that a TSP with different costs for edge{a,b}
> and edge{b,a} can be reduced to a (larger) TSP with edge{a,b} =
> edge{b,a}. This limits the right side of the equality-relation in
> min() to the factorial of the vertices.

if that reduction is correct, this actually solves for N in TSPs where
edge costs can be derived only from the coordinates of the vertices on
a plane.

(if duble post I am sorry, this did not post correctly 30 minutes later
for my reader)
mathisart wrote:
> Rados³aw Hofman wrote:
> I think I read somewhere that a TSP with different costs for edge{a,b}
> and edge{b,a} can be reduced to a (larger) TSP with edge{a,b} =
> edge{b,a}. This limits the right side of the equality-relation in
> min() to the factorial of the vertices.

if that reduction is correct, this actually solves for N in TSPs where
edge costs can be derived only from the coordinates of the vertices on
a plane.

tchow{}lsa.umich.edu napisał(a):
> In article <ekeke3$3t7$1{}sunflower.man.poznan.pl>,
> Rados³aw Hofman <radekh{}teycom.pl> 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*).

Hi,

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? If we narrow domain of possible dates then it
is (for example in gramma rules of language). That's why I am not sure
if uniqueness is property of language.

> >- 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)?



I'm not trying to convince anyone that mine considerations about UP are
correct (or worth reading) and I don't even claim then I understand
this class well. I think then that there is no need for HUP .

I started to write about UP because I was a bit scared with corollaries
of transformation from TSP to UniqueTSP. I knew nothing about UP so I
have started to read - after some ACM articles about it I still feel
like I'm still missing something. Maybe somebody could provide us all
with example of UP language?

Best regards,

Radek Hofman

PS. Things are named after those who named it first (example - Columb
discovered America but it is named after Amerigo Vespucci, who named
new land "a continent". So class you mentioned should be called ChUP

Radoslaw Hofman napisa³(a):
> I started to write about UP because I was a bit scared with corollaries
> of transformation from TSP to UniqueTSP.

I ment that I was scared with corollaries some of people made from this
transformation - not mine own thoughts :-))))

Best regards,

Radek Hofman

tchow{}lsa.umich.edu wrote:
> --
> Tim Chow tchow-at-alum-dot-mit-dot-edu

Tim,

Could U pls advise whether this Question for the TSP is also
NP-Complete: -
"Does there exist a TSP tour of length = C ??"

I have checked many references on Google, but they do not mention about
the "only =" version. They only state that " < = " version is
NP-Complete, i.e. "Does there exist a TSP tour of length <= C ??"

If you know any "strong" references stating that the "only =" version
Question is also NP-Complete, could you please let us know.

By strong, I mean something from some very reputed Journal, or some
lecture notes from MIT/Harvard/etc. By the way, I did a Google search
and I came across a CACHED version of one lecture note from MIT -
<http://theory.lcs.mit.edu/~madhu/FT99/lect1.ps> page 4. Here, in the
second para under the heading "3.3 NP-Optimization Problems", it says
something. Unfortunately I do not have the .PS reader in my PC (and the
above file happens to be .PS), so I am unable to read the special
symbols (like = or <=) what they are saying.

Could u please help me find some strong references, which say whether
the "only =" version is also NP-Complete.

deepakc napisal(a):
> tchow{}lsa.umich.edu wrote:
> > --
> > Tim Chow tchow-at-alum-dot-mit-dot-edu
>
> Tim,
>
> Could U pls advise whether this Question for the TSP is also
> NP-Complete: -
> "Does there exist a TSP tour of length = C ??"
>
> I have checked many references on Google, but they do not mention about
> the "only =" version. They only state that " < = " version is
> NP-Complete, i.e. "Does there exist a TSP tour of length <= C ??"
>
> If you know any "strong" references stating that the "only =" version
> Question is also NP-Complete, could you please let us know.
>
> By strong, I mean something from some very reputed Journal, or some
> lecture notes from MIT/Harvard/etc. By the way, I did a Google search
> and I came across a CACHED version of one lecture note from MIT -
> <http://theory.lcs.mit.edu/~madhu/FT99/lect1.ps> page 4. Here, in the
> second para under the heading "3.3 NP-Optimization Problems", it says
> something. Unfortunately I do not have the .PS reader in my PC (and the
> above file happens to be .PS), so I am unable to read the special
> symbols (like = or <=) what they are saying.
>
> Could u please help me find some strong references, which say whether
> the "only =" version is also NP-Complete.

Hi,

Does it make any difference? We can transform every NP problem to HC
and then build TSP with question PATH==N, that means that every NP
problem can be transformed to version having == in question.

In mine opinion <= is used to show that we are asking for optimal tour
instead of tour of size N, but it does not matter for me.

Cheers,

Radek Hofman