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 20061122, 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
problem.
Why would you think this?
Because you are basically saying that:
a) Dividing the original TSP into smaller tours is the fastest way
b) HeldKarp 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
specific?
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
HeldKarp algorithm in speed. I'm only claiming that there are no
algorithms which can *beat* the HeldKarp algorithm in speed.
Craig

// Antti Virtanen // http://lokori.iki.fi/ // 0504004278
.
 FollowUps:
 Re: An easy way to prove P != NP
 From: mathisart
 Re: An easy way to prove P != NP
 From: Radoslaw Hofman
 Re: An easy way to prove P != NP
 References:
 An easy way to prove P != NP
 From: Craig Feinstein
 Re: An easy way to prove P != NP
 From: Craig Feinstein
 Re: An easy way to prove P != NP
 From: Patricia Shanahan
 Re: An easy way to prove P != NP
 From: Craig Feinstein
 Re: An easy way to prove P != NP
 From: Antti Virtanen
 An easy way to prove P != NP
 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
 Index(es):
Relevant Pages
