Re: P=NP: Linear Programming Formulation of the TSP

On 2005-04-25, Yajun <yalding@xxxxxxxxx> wrote:
> Isn't it a solved problem that TSP CAN NOT be formulated into a Linear
> Programming that can be solved in polynomial time?
>
> I heard some story from my advisor. There was a professor in Canada
> tried to formulate TSP using LP to prove P=NP. He had several versions
> of papers about it, of course, there were alway flaws in. Later on,
> some authors from Japan proved that this method will not work.
>
> Forgive me for this non-academic description. Maybe some people here
> can give some references about this story, :)
>
> regards,
> yalding
>
There was certainly a professor from Canada who claimed to have proved
P=NP but using a linear programming formulation of graph isomorphism.
I proved that this couldn't work (Technical report: On Linear Programming,
Graph Isomorphism and NP-Complete Problems,
TR-CS-93-03, Department of Computer Science,
Australian National University).
Maybe you heard a slightly garbled version of this story?

J.M. (Mike Robson).
.

Relevant Pages

  • Re: Canadians spent $832 for TV programming in 2007
    ... Where in Canada do you live that you have more options and programming than the average American? ... I get more programming (Canadian and American) as well as more options as to when to view them. ... Right now, it includes some 6 packages including news, sports, all the movie channels and all the HD I want to make sure I can see every crease in Tom Brady's butt. ...
    (rec.arts.tv)
  • Re: Computer Interface for VC2 Board
    ... Could you please give the names of 2 dealers in Canada who will sell ... me a legal subscription to HBO and Showtime ... >> is forced to extreme measures to watch programming from C band ... > there are Canadian DTH providers that offer much of what is on US cable ...
    (rec.video.satellite.tvro)
  • Re: wow--what a lineup on my Retro station
    ... 12noon-Local programming ... 12pm Alfred Hitchcock Hour ... 4:00PM - Magnum, P.I. ... I'm in Canada and not sure if I can get the OTA 7.4 station, ...
    (rec.arts.tv)
  • Re: Computer Interface for VC2 Board
    ... > me a legal subscription to HBO and Showtime ... >>> is forced to extreme measures to watch programming from C band ... There are a number of them in Canada, ...
    (rec.video.satellite.tvro)
  • Re: knights tour
    ... and both are backtracking algorithms: ... MIP (Mixed Integer linear programming) ... constraint programming should be the better ...
    (comp.theory)