# 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

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) 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

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

Held-Karp algorithm in speed. I'm only claiming that there are no

algorithms which can *beat* the Held-Karp algorithm in speed.

Craig

--

// Antti Virtanen -//- http://lokori.iki.fi/ -//- 050-4004278

.

**Follow-Ups**:**Re: An easy way to prove P != NP***From:*mathisart

**Re: An easy way to prove P != NP***From:*Radoslaw Hofman

**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

- 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):