Re: An easy way to prove P != NP
- From: "Craig Feinstein" <cafeinst@xxxxxxx>
- Date: 23 Nov 2006 13:46:41 -0800
Antti Virtanen wrote:
On 2006-11-22, Craig Feinstein <cafeinst@xxxxxxx> wrote:
See http://arxiv.org/abs/cs.CC/0611082 for a completely formal version
of my argument that I gave here a few weeks ago in this thread.
I challenge anyone to find a hole.
As far as I can tell, it is limited to certain forms of algorithms,
those that operate by solving subproblems of similar form to the main
Why would you think this?
Because you are basically saying that:
a) Dividing the original TSP into smaller tours is the fastest way
b) Held-Karp is the fastest possible algorithm to calculate the subproblems
I don't understand where the proof for statement a) is. I'm not saying you
are wrong, but I don't see how to conclude that. Seems I'm not the only one.
I'm not sure how statement a) relates to my paper. Can you be more
I should remind you that my paper never claims that there aren't any
other types of algorithms for solving the TSP which can match the
Held-Karp algorithm in speed. I'm only claiming that there are no
algorithms which can *beat* the Held-Karp algorithm in speed.
// Antti Virtanen -//- http://lokori.iki.fi/ -//- 050-4004278
- Prev by Date: Re: An easy way to prove P != NP
- Next by Date: Re: Discussion regarding Mr. Diabys algorithm
- Previous by thread: Re: An easy way to prove P != NP
- Next by thread: Re: An easy way to prove P != NP