# 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 2006-11-22, 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) 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

.

**Follow-Ups**:**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

**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

- 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):