Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!ira.uka.de!braun
From: braun@ira.uka.de (Heinz Braun)
Newsgroups: comp.theory
Subject: Solution of TSP - P=NP now very probable ?
Message-ID: <1991Mar20.133401.24801@ira.uka.de>
Date: 20 Mar 91 13:34:01 GMT
Sender: news@ira.uka.de (USENET News System)
Organization: University of Karlsruhe, FRG
Lines: 15

In the german newspaper "Die Zeit" (March 14, 1991) Th. von Randow
reported on recent work of Donald L. Miller and Joseph F. Penky on the
Travelling Salesman Problem. Von Randow claims that they have made a big
step towards the solution of TSP by discovering a polynomial algorithm
for an important special case of TSP. Furthermore von Randow even suggests that
P=NP became much more probable by their work.
Does anybody know more details about the problem they really solved ?

Heinrich Braun
Institut fuer Logik, Komplexitaet
und Deduktionssysteme
Universitaet Karlsruhe
Postfach 6980
D 7500 Karlsruhe (FRG)
email: braun@ira.uka.de