Sorry, an error occurred while loading the content.

## Re: 10^12000+3213 and P =/= NP

Expand Messages
• 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
Message 1 of 18 , Mar 29, 2001
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

> 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
• ... 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
Message 2 of 18 , Mar 29, 2001
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
• ... History is always moot. Jack Edmonds paper on matroids was clearly influential, as Cook says in the Clay 2000 PDF formulation to which I directed you. ...
Message 3 of 18 , Mar 29, 2001
Milton Brown wrote:

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

History is always moot. Jack Edmonds paper on matroids
was clearly influential, as Cook says in the Clay 2000
PDF formulation to which I directed you.

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

Yes, these too are mentioned in the recent offering
by Cook.

Thanks for correcting Levinson [sic] to Levin.
You set me on a right royal goose chase
with the former!

David
• ... Milton s right this time. Cook came up with NP-completeness. +--------------------------------------------------------+ ...
Message 4 of 18 , Mar 30, 2001
At 09:30 PM 3/29/2001 -0800, Milton Brown wrote:

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

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

+--------------------------------------------------------+
| Jud McCranie |
| |
| 137*2^261147+1 is prime! (78,616 digits, 5/2/00) |
+--------------------------------------------------------+
• ... Thanks, Jud. I uncritically accepted the final sentence of http://www.claymath.org/prizeproblems/pvsnp.htm Stephen Cook formulated the P versus NP problem
Message 5 of 18 , Mar 30, 2001
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
Your message has been successfully submitted and would be delivered to recipients shortly.