Re: An easy way to prove P != NP



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/

.