🚀 go-pugleaf

In article <gordon.726823495@ningaui>, gordon@cs.uwa.oz.au (Gordon Royle) writes:
> In <pcw.726468672@digex> pcw@access.digex.com (Peter Wayner) writes:
> 
> >core of the problem. We already have neat algorithms that get close to
> >the right answer on NP-complete problems like the travelling salesman.
> >For all practical intents and realistic purposes, this is enough.It's
> >really just an academic question now.
> 
> 
> Is this true? I am not aware of any decent algorithms for Travelling 
> Salesman at all. In fact G&J show that there cannot be any polynomial
> time approximation algorithms for Travelling Salesman that achieve
> ANY given multiple of the optimal solution (page 147).   
> Does this not contradict the above statement, or am I labouring under a 
> delusion? 
> 
> 
> Gordon
Peter Wayer's statement is not true. We do have algorithms that give in general
good solutions for the TSP, but we cannot say anything about the quality in
general of any solution produced. Indeed such algorithms may in 95% of the cases
approach the optimal solution by 90%. But we cannot guarantee 100% of the cases.
Furthermore, we do not have any possibility to check if a given solution is
within the 95% of good solutions or not.

But TSP is not the only NP-complete problem. There are other problems like Max
Clique that even cannot be approximated within any constant, e.g. approxiating is
as hard as solving.

Therefore I think the P?=NP question is not ony of theoretical interesed.

Claude

---------------------------------------------------------------------------
Claude G. Diderich                            Internet: diderich@di.epfl.ch
30, Avenue S.Reymondin  --  CH-1009 Pully (VD)  --  Switzerland  --  Europe

``Imagination is more important than knowledge''            Albert Einstein
---------------------------------------------------------------------------