Re: Discussion about transformation TSP to UniqueTSP


tchow@xxxxxxxxxxxxx napisał(a):
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*).

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

.

Relevant Pages

  • Re: ZFC? countable?uncountable?
    ... so here existance is used in the sense of referrability to something. ... Existance by uniqueness. ... For any term 'T' in the language, ... Robin hood here, Thus Robin hood exists?Strange? ...
    (sci.math)
  • Re: ZFC? countable?uncountable?
    ... Existance by uniqueness. ... For any term 'T' in the language, ... Robin hood here, Thus Robin hood exists?Strange? ...
    (sci.math)
  • Similarities of music to language:
    ... spoken or written language, ... Prepositions - NONE ... not as case inflections.] ... Genitive (relationships by transformations) ...
    (rec.music.classical.contemporary)
  • Re: Discussion about transformation TSP to UniqueTSP
    ... We know that forall instances (strings) of every NP problem ... string in NP-complete language must be result of transformation. ... words transformations is like function. ...
    (comp.theory)
  • Re: NP with oracle machines
    ... I have a question pertaining to the complexity class NP and oracle ... oracle machine, say one for SAT or TQBF. ... if I am dealing with a language/decision problem that is ... But if I am dealing with a language in NP^TQBF, ...
    (comp.theory)