# Re: An easy way to prove P != NP

*From*: gwoegi@xxxxxxxxxxxxxxxxxxxxxx (GJ Woeginger)*Date*: 26 Nov 2006 14:45:13 GMT

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/

.

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

**Re: An easy way to prove P != NP***From:*Craig Feinstein

- Prev by Date:
**Re: An easy way to prove P != NP** - Next by Date:
**Re: Discussion regarding Mr. Diabys algorithm** - Previous by thread:
**Re: An easy way to prove P != NP** - Next by thread:
**Re: An easy way to prove P != NP** - Index(es):