Re: An easy way to prove P != NP


Patricia Shanahan wrote:
Craig Feinstein wrote:
Patricia Shanahan 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.

--
// Antti Virtanen -//- http://lokori.iki.fi/ -//- 050-4004278
That is one of my main reasons for thinking it.

The other is that something called "the Dynamic Programming Principle"
is used in the proof as though it were a theorem, without any reference
to a paper proving it. It is treated as though it should be so well
known that it does not need proof.

It's something that I never really thought anyone would question. It
seems very obvious to me that if there is a problem to find the minimum
value of a set in which all of its members are possible candidates for
the minimum value and you have an algorithm which can compute all of
the members in the set in the fastest way possible and then select the
minimum value in the set, then you can't beat that algorithm in speed
for solving the problem.

It is not at all obvious to me, and seems to be the key to your paper.
Please supply a proof, either directly or by providing a link to a paper
with a more formal statement and a proof.

It's explained in the paper above the statement of the "Dynamic
Programming Principle".


Patricia

.

Relevant Pages

  • Re: An easy way to prove P != NP
    ... GJ Woeginger wrote: ... # the members in the set in the fastest way possible and then select the ... # minimum value in the set, then you can't beat that algorithm in speed ... All members of S are possible candidates for the minimum. ...
    (comp.theory)
  • Re: An easy way to prove P != NP
    ... the members in the set in the fastest way possible and then select the ... then you can't beat that algorithm in speed ... of finding the shortest path between two vertices s and t in a graph--- ... that any algorithm for finding the shortest path must take exponential time. ...
    (comp.theory)
  • Re: An easy way to prove P != NP
    ... the members in the set in the fastest way possible and then select the ... then you can't beat that algorithm in speed ... of finding the shortest path between two vertices s and t in a graph--- ... certain types of algorithms isn't really that surprising. ...
    (comp.theory)
  • Re: An easy way to prove P != NP
    ... the members in the set in the fastest way possible and then select the ... then you can't beat that algorithm in speed ... of finding the shortest path between two vertices s and t in a graph--- ... that any algorithm for finding the shortest path must take exponential time. ...
    (comp.theory)
  • Re: An easy way to prove P != NP
    ... I wrote in response to Patricia Shanahan earlier: ... the members in the set in the fastest way possible and then select the ... then you can't beat that algorithm in speed ...
    (comp.theory)