Re: An easy way to prove P != NP
- From: "Craig Feinstein" <cafeinst@xxxxxxx>
- Date: 7 Dec 2006 11:01:49 -0800
GJ Woeginger wrote:
Craig Feinstein <cafeinst@xxxxxxx> wrote:
#
# 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.
#
This statement is obvious to YOU, since you are working and
thinking in your own Feinstein model of computation.
On the other hand, your statement is clearly false in all
classical models of computation.
Consider the problem of minimizing a convex function f over the
integers in the set S={1,2,...,2^n}.
1. The problem is to find the minimum value of a set.
(Exactly as you wrote.)
The set is {f(1),...,f(2^n)}.
2. All members of S are possible candidates for the minimum.
(Exactly as you wrote.)
3. We have an algorithm which can compute all of the members
in the set in the fastest way possible.
(Exactly as you wrote.)
Just evaluate f at the integers in S.
4. Then select the minimum value in the set.
(Exactly as you wrote.)
Okay. This takes you 2^n steps.
5. Then you can't beat that algorithm in speed for solving the problem.
(Now that's one of the Feinstein axioms.)
To summarize, in the Feinstein model of computation, you cannot compute
the minimum of f over S in fewer than 2^n steps.
But in the classical models of computation, you can use (for instance)
Fibonacci-Search to minimize f (substantially!) faster.
--Gerhard
___________________________________________________________
Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/
Gerhard,
You are correct! Mazel Tov. Actually, when I said, "All members of S
are possible candidates for the minimum", I meant that all members of S
are possible candidates for the minimum until they are evaluated. My
statement was ambiguous.
I've just withdrawn my paper from arxiv.org. The problem I see with my
paper has to do with the fact that I am proving that the non-uniform
version of the Held-Karp algorithm has the fastest running-time of all
algorithms for solving the TSP in a RAM model of computation. I now am
not so certain this is true for RAM, which is why I withdrew it.
In any case, if my paper is wrong, I think it is good to understand
why. Perhaps you could enlighten us, since proving lower-bounds for
non-uniform algorithms was something which came up in past threads when
you critiqued my paper?
Thank you,
Craig
.
- Follow-Ups:
- Re: An easy way to prove P != NP
- From: Patricia Shanahan
- Re: An easy way to prove P != NP
- From: Bryan Olson
- Re: An easy way to prove P != NP
- Prev by Date: Flow Decomposition
- Next by Date: Quantum Computation By Adiabatic Evolution
- 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
|
