Re: An easy way to prove P != NP




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?

.