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

.



Relevant Pages

  • Re: Find closest matching name
    ... > The distance between two strings that is often used is the Levenshtein ... You can find information on the algorithm from Google. ... One way to implement dynamic programming as a depth first search ... which has been implemented in Java as "Jazzy". ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Does Prolog do Dynamic Programming automatically?
    ... some optimization sweep algorithm. ... I tried the "memoization" Dynamic Programming algorithm that is on the ... Prolog Wikipedia page in the context of one of my own programs, ... about making memoization efficient. ...
    (comp.lang.prolog)
  • Re: Does Prolog do Dynamic Programming automatically?
    ... some optimization sweep algorithm. ... I tried the "memoization" Dynamic Programming algorithm that is on the ... Prolog Wikipedia page in the context of one of my own programs, ...
    (comp.lang.prolog)
  • Re: How to approach
    ... because I can't come up with an algorithm to do it. ... One of the problems was, given an imaginary chess piece, a board nXn dimensions and a starting and ending location, and a number of moves, tell me how many unique ways there are to get from the starting to ending position ... "Dynamic programming" is one of several ...
    (comp.lang.java.programmer)
  • Re: An easy way to prove P != NP
    ... The other is that something called "the Dynamic Programming Principle" ... of dynamic programming algorithms. ... of my own ignorance and lack of web search skills. ...
    (comp.theory)