Re: Discussion about transformation TSP to UniqueTSP
- From: "mathisart" <artrigue@xxxxxxxxx>
- Date: 28 Nov 2006 10:41:25 -0800
On Nov 28, 2:36 am, "Radoslaw Hofman" <rad...@xxxxxxxxx> wrote:
t...@xxxxxxxxxxxxx napisał(a):
In article <ekeke3$3t...@xxxxxxxxxxxxxxxxxxxxxxx>,
Rados³aw Hofman <rad...@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*).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.
The original transformation suffices for #2, provided you dont have to
find the total cost C' of the tour for the unique TSP, from the
original TSP's C cost. #3 doesn't look to be difficult in any way, to
get to the same place:
Solve the TSP as though all edges have the same weight -- this is
polynomial. Take the edges in (any) solution and create a new TSP from
only those edges (including their integer costs). This TSP has the
form that for all vertices, each vertex has 2 edges, and each edge is
necessary in the solution. This TSP also has a solution iff the
original TSP has a solution, and the total cost for the decision
problem C' is exactly definable in polynomial time (though not relative
to C, it is relative to the original's edge costs).
.
- References:
- Discussion about transformation TSP to UniqueTSP
- From: Radosław Hofman
- Re: Discussion about transformation TSP to UniqueTSP
- From: tchow
- Re: Discussion about transformation TSP to UniqueTSP
- From: Radoslaw Hofman
- Discussion about transformation TSP to UniqueTSP
- Prev by Date: Re: Discussion about transformation TSP to UniqueTSP
- Next by Date: Re: Is there a known algorithm to solve this "playoff ranking" problem?
- Previous by thread: Re: Discussion about transformation TSP to UniqueTSP
- Next by thread: Re: Discussion about transformation TSP to UniqueTSP
- Index(es):
Relevant Pages
|
