Browse Groups

• ## Re: [PrimeNumbers] 10^12000+3213 and P =/= NP

(18)
• NextPrevious
• ... You re stating this without any proof or evidence: But, primes are not decidable in polynomial time, example of this number and infinitely many others.
Message 1 of 18 , Mar 29, 2001
View Source
At 08:09 PM 3/29/2001 -0800, Milton Brown wrote:
>How specifically is it wrong?

You're stating this without any proof or evidence:

"But, primes are not decidable in polynomial time,
example of this number and infinitely many others.
Therefore, primes are not in P."

Do you have a proof that it can't be decided if a number is prime in poly
time? If the ERH is true, they are in P. Even w/o the ERH, there are
algorithms (Adleman-Pomerance-Rumley and variations) that are very close to
poly, and definitely sub-exponential, whereas all known algorithms for all
NP-complete problems are exponential.

>Could you define "knowledgeable person"?

A person familiar with these topics.

+--------------------------------------------------------+
| Jud McCranie |
| |
| 137*2^261147+1 is prime! (78,616 digits, 5/2/00) |
+--------------------------------------------------------+
• 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 2 of 18 , Mar 29, 2001
View Source
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 3 of 18 , Mar 29, 2001
View Source
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 4 of 18 , Mar 29, 2001
View Source
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 5 of 18 , Mar 30, 2001
View Source
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 6 of 18 , Mar 30, 2001
View Source
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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.