Re: An easy way to prove P != NP
 From: "Craig Feinstein" <cafeinst@xxxxxxx>
 Date: 23 Nov 2006 13:29:21 0800
Patricia Shanahan wrote:
Antti Virtanen wrote:
On 20061122, Craig Feinstein <cafeinst@xxxxxxx> wrote:
Why would you think this?See http://arxiv.org/abs/cs.CC/0611082 for a completely formal versionAs far as I can tell, it is limited to certain forms of algorithms,
of my argument that I gave here a few weeks ago in this thread.
I challenge anyone to find a hole.
those that operate by solving subproblems of similar form to the main
problem.
Because you are basically saying that:
a) Dividing the original TSP into smaller tours is the fastest way
b) HeldKarp 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/ // 0504004278
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 was not mentioned, in that form, as a theorem in an algorithm design
course I took a few years ago, although the course covered both dynamic
programming and the lower bound on complexity of comparison sorts.
I've looked in textbooks. I've searched on the web. The closest I have
found is Richard Bellman's "dynamic programming principle", in e.g.
http://cs.nyu.edu/~yap/classes/funAlgo/05f/lect/l7.pdf
But in the forms I've found so far Bellman's dynamic programming
principle only makes claims about the correctness, in the sense of
finding the minimum cost solution, of dynamic programming algorithms. It
does not say anything about their performance optimality. In that form,
I do think it is both wellknown, and obvious once you hear it.
Of course, my inability to find the theorem in the form in which it is
used in http://arxiv.org/abs/cs.CC/0611082 could just be a manifestation
of my own ignorance and lack of web search skills.
Regardless, the use of the stated "dynamic programming principle" as a
theorem about the lower bound of computational complexity of all regular
algorithms needs to be justified either by proof in the paper, or by
reference to a paper that proves it, in exactly the form in which it is
used.
I am the one who gave this concept the name, "dynamic programming
principle", because the HeldKarp algorithm is a dynamic programming
algorithm. Perhaps I should have not given it that name to avoid
confusion.
Patricia
.
 FollowUps:
 Re: An easy way to prove P != NP
 From: GJ Woeginger
 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: tchow
 Re: An easy way to prove P != NP
 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: Patricia Shanahan
 An easy way to prove P != NP
 Prev by Date: Re: Discussion regarding Mr. Diabys algorithm
 Next by Date: Re: An easy way to prove P != NP
 Previous by thread: Re: An easy way to prove P != NP
 Next by thread: Re: An easy way to prove P != NP
 Index(es):
Relevant Pages
