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?

.



Relevant Pages

  • Re: another proof that p is not np
    ... You should know that the algorithm in my paper is the fastest-known ... exact algorithm for solving subset-sum, so the idea of trying to prove ... > solves each subproblem in the fastest way possible by the induction ... > obtained from solving any one of the subproblems to save time solving ...
    (comp.theory)
  • Re: Question: the modern/state-of-the-art P?=NP research
    ... The strategy is to prove that the fastest known algorithm that solves ... the subset-sum problem, found in the paper Woeginger, G.J., ``Exact ... I make the observation that solving a problem ... calculated and used to solve both subproblems (in order to save time, ...
    (comp.theory)
  • Re: An easy way to prove P != NP
    ... I don't say that giving weigths is disabled in instance. ... instance without weights but only with binary encoded n then it had ... Then if algorithm checks in first step are weigths ... But the counterexample's subproblems ...
    (comp.theory)
  • Re: An easy way to prove P != NP
    ... So you only talk about lower bound for algorithm not problem. ... faster worst-case asymptotic running-time in the RAM ... Programming Principle - Suppose that problem P is to find the minimum value ... algorithm A solves each of these subproblems in the minimum running-time ...
    (comp.theory)