- David,

The reason I was confused seems to be your statemnt:

"Anyone who thinks that is is easy to decide whether

P is or is not the same as NP should read Cook,

who invented the question."

My books say " ... Edmonds[61], who also introduced the

class NP and conjectured that P =/= NP" not Cook,

see "Algorithms" by Cormen et. al. page 963.

Perhaps you have a better reference.

Cook and Levin gave NP completeness proofs for things like 3SAT,

same reference.

Milton L. Brown

d.broadhurst@... wrote:

> Milton Brown wrote:

>

> > I thought you meant the proof of the

> > Cook-Levinson Theorem.

>

> Sorry, I don't know that theorem.

>

> Norman Levinson did many fine things,

> such as his work on the zeros of the Riemann

> zeta function and his famous letter to Stephen Smale,

> which kick-started chaos theory,

> but MathSciNet drew a blank on Cook+Levinson.

>

> I know that Leonid Levin did work on computational

> complexity that relates directly to (but does not answer)

> Stephen Cook's question.

>

> Can you please supply a journal

> reference to "Cook-Levinson theorem"?

>

> Thanks

>

> David - Milton Brown wrote:

> I thought you meant the proof of the

Sorry, I don't know that theorem.

> Cook-Levinson Theorem.

Norman Levinson did many fine things,

such as his work on the zeros of the Riemann

zeta function and his famous letter to Stephen Smale,

which kick-started chaos theory,

but MathSciNet drew a blank on Cook+Levinson.

I know that Leonid Levin did work on computational

complexity that relates directly to (but does not answer)

Stephen Cook's question.

Can you please supply a journal

reference to "Cook-Levinson theorem"?

Thanks

David - Milton Brown wrote:

> My books say " ... Edmonds[61], who also introduced the

History is always moot. Jack Edmonds paper on matroids

> class NP and conjectured that P =/= NP" not Cook,

> see "Algorithms" by Cormen et. al. page 963.

was clearly influential, as Cook says in the Clay 2000

PDF formulation to which I directed you.

> Cook and Levin gave NP completeness proofs

Yes, these too are mentioned in the recent offering

> for things like 3SAT

by Cook.

Thanks for correcting Levinson [sic] to Levin.

You set me on a right royal goose chase

with the former!

David - At 09:30 PM 3/29/2001 -0800, Milton Brown wrote:

>My books say " ... Edmonds[61], who also introduced the

Milton's right this time. Cook came up with NP-completeness.

>class NP and conjectured that P =/= NP" not Cook,

>see "Algorithms" by Cormen et. al. page 963.

+--------------------------------------------------------+

| Jud McCranie |

| |

| 137*2^261147+1 is prime! (78,616 digits, 5/2/00) |

+--------------------------------------------------------+ - Jud McCranie wrote:
> Milton's right this time. Cook came up with NP-completeness.

Thanks, Jud.

I uncritically accepted the final sentence of

http://www.claymath.org/prizeproblems/pvsnp.htm

"Stephen Cook formulated the P versus NP problem in 1971."

Happy to accept your better informed judgement.

David