Re: An easy way to prove P != NP




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

.



Relevant Pages

  • Re: An easy way to prove P != NP
    ... 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 ... Because you are basically saying that: ...
    (comp.theory)
  • Re: An easy way to prove P != NP
    ... 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 ... Because you are basically saying that: ... algorithms which can *beat* the Held-Karp algorithm in speed. ...
    (comp.theory)