I already know that the topic doesn't have a lot of

practical interest.

But I hope this can have certain theoretical interest.

This perhaps could help somebody to find an algorithm

but efficient.

--- Phil Carmody <

thefatphil@...> escribió: >

--- Sebastian Martin <

sebi_sebi@...> wrote:

> > The computational complexity is (nlogn)^3 for the

> > problem 38 formulas, I have not studied the

> complexity

> > for the problem 39.

> > And the formulas in the article primes in an

> aritmetic

> > progression is also polinomial.

>

> It depends on how you judge the size of the problem,

> I should have been more

> explicit. It's fairly common to view the size of a

> problem parametrised by

> the number N as log(N). O(poly(N)) is exponential in

> log(N).

>

> For example, consider the discussions surrounding

> the recent AKS algorithm.

> Trial division to sqrt(N) is sub-linear in N, but is

> expoential in log(N).

> Trial division would never be described as a

> sub-linear algorithm in any

> context I've encountered.

>

> Sieving, however, adopts a 'N is linear'

> nomenclature, as does prime

> counting, so I did probably chose the wrong default

> (oh the joys of having

> two defaults).

>

> With that in mind - can you explain why a contrived

> O(n^(3+eps)) algorithm

> has any practical merit when there exist

> O(n^(1+eps)) algorithms or better

> that do the same job?

>

> I am reminded of the classic 'grand revolutionising

> factoring algorithm':

>

>

http://groups.google.com/groups?th=621fa55443f7d8b3&rnum=1 > which was subsequently 'pessimised' in the

> follow-ups.

>

>

> Phil

>

>

>

> =====

> "The hottest places in Hell are reserved for those

> who, in

> times of moral crisis, preserved their neutrality."

> -- John F. Kennedy, 24 June 1963, claiming to quote

> Dante,

> to whom this has been incorrectly attributed ever

> since.

>

> __________________________________________________

> Do You Yahoo!?

> Yahoo! Finance - Get real-time stock quotes

> http://finance.yahoo.com

>

_______________________________________________________________

Yahoo! Messenger

Nueva versión: Webcam, voz, y mucho más ¡Gratis!

Descárgalo ya desde

http://messenger.yahoo.es