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/

.



Relevant Pages

  • Re: An easy way to prove P != NP
    ... If we need the "principle of commutational adjustment," and the rest ... there is no algorithm with a faster running-time. ... G.J. Woeginger takes the point of view that Feinstein has his own ... because the Feinstein model assumes each case requires individual ...
    (comp.theory)
  • Feinsteins paper on the Collatz problem was Re: Raatikainens critique of Chaitin
    ... >> Your paper on the Collatz is wrong, Mr Feinstein. ... A smarter algorithm that Feinstein's ... I note that Mr Feinstein has already withdrawn three papers from the arXiv. ...
    (sci.math)
  • Re: Complexity Theory for Simpletons
    ... I mean that algorithm A is "the best algorithm for solving ... There is a famous result by Meyer auf der Heide, ... The work of Feinstein claims that every such algorithm must use at ...
    (comp.theory)