RE: RE: Notebook for Primes
- To: mathgroup at smc.vnet.net
- Subject: [mg36050] RE: [mg36023] RE: [mg35992] Notebook for Primes
- From: "DrBob" <majort at cox-internet.com>
- Date: Wed, 14 Aug 2002 05:35:18 -0400 (EDT)
- Reply-to: <drbob at bigfoot.com>
- Sender: owner-wri-mathgroup at wolfram.com
>>The sieve method is not polynomial in the size of the number. Polynomial in the number, yes, but exponential in the size (logarithm) of the number. Point taken, but polynomial complexity is often overrated anyway. I've had students tell me a problem can't be solved, simply because the algorithm is exponential. The Simplex algorithm for linear programs is exponential worst-case, but very fast in practice. Meanwhile, it is reputed that the FIRST polynomial time algorithm began with a prohibitive fixed setup cost: "Let there be light." Bobby Treat -----Original Message----- From: danl at wolfram.com [mailto:danl at wolfram.com] To: mathgroup at smc.vnet.net Subject: [mg36050] Re: [mg36023] RE: [mg35992] Notebook for Primes DrBob wrote: > > The oldest algorithm for testing primes... the Sieve of Eratosthenes... > is polynomial and deterministic. It's simply too slow to use, just like > the one at the attachment. > > Bobby > > -----Original Message----- > From: Jeff Dillon [mailto:jeffdi at fidalgo.net] To: mathgroup at smc.vnet.net > Subject: [mg36050] [mg36023] [mg35992] Notebook for Primes > > Is there a publicly available Mathematica 3.0 notebook that implements > the Primes is in P? > > http://www.msnbc.com/news/792126.asp The sieve method is not polynomial in the size of the number. Polynomial in the number, yes, but exponential in the size (logarithm) of the number. The algorithm recently making waves appears not to be practical as yet. A variant proposed at the end of the draft article, based on an unproven conjecture of the authors, would possibly be viable as it would bring the suspected complexity exponent from 6 to 3. I imagine we will either hear of such improvements, or, at the least, get new pseudoprime algorithms, based on such variants of this new deterministic algorithm. Daniel Lichtblau Wolfram Research