# Re: An easy way to prove P != NP

*From*: "mathisart" <artrigue@xxxxxxxxx>*Date*: 25 Nov 2006 07:34:59 -0800

Craig Feinstein wrote:

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.

You make the implicit assumption that dividing the TSP into subproblems

in just such a way, makes maximum use of information available about

the general problem. Mr (Dr?) Hofman's main question about 2SAT is Mrs

(Dr?) Shanahan's question about equally weighing puppies [what an

awesome example we have to work with! who doesn't love puppies?], is

Virtanen's request for proof of a) -- how do you know that you make

maximum use of the information, in your formulation of the TSP problem?

This is the if statement of your Dynamic programming Principle:

If an algorithm that solves each of

the n-2 subproblems in the fastest way possible makes

optimal use of such information, then the algorithm will

not perform any unnecessary computations when solv-

ing each of the subproblems and will therefore solve the

TSP in the fastest way possible.

Back to the puppies! If you measure your weight once, it makes maximum

use. If you know in advance that 9 of the puppies weigh the same,

holding many puppies at once can speed things up. You don't just make

maximum use of the information in the smallest/simplest instance,

that's just what any one puppy can weigh! You make use of information

in all larger instances of the problem... that is the "such

information".

It is known that you cannot work on different-but-equivalent

formulations of the TSP polytope in LP, but not in general! And the

ability to reduce something into a form soluable by recursively solving

it's simplest/smallest instances is in no way a proof that the

reduction is best.

Don't think that you need to show the H-K algorithm is fastest in

general. If there is a faster method, that then can be plugged into

your argument, with a slightly adjusted bounds. But do consider: is

there is no further information to make use of in the structure of the

problem?

.

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

**Re: An easy way to prove P != NP***From:*Craig Feinstein

- Prev by Date:
**Re: Discussion regarding Mr. Diabys algorithm** - 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):