Re: An easy way to prove P != NP




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 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 well-known, 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 Held-Karp algorithm is a dynamic programming
algorithm. Perhaps I should have not given it that name to avoid
confusion.


Patricia

.