Re: A little bomb ?

[Bruno Marchal]

Saibal Mitra:

>I think that a polynomial time algorithm means that the algorithm's running
>time is a polynomial in
>  Log(n)/Log(2), not n, because the size of the input matters, not the value
>of the number.


That makes sense. You could have said polynomial in log(n) I suppose.
I guess it is in that sense that it is said that PRIMES has been proved
being in P with Riemann hypothesis(*). And that a polynomial probabilistic
algorithm has been find (Solovay and Strassen (**)).
Thanks,

Bruno

(*) http://www.claymath.org/prizeproblems/riemann.htm
(**) http://cui.unige.ch/tcs/cours/crypto/crypto8/node6.html

Re: A little bomb ?

[Saibal Mitra]

Bruno wrote:

> More seriously I do no more know what exactly is new in that papers
> on the primes.
> Here a message I got from friends. I currently agree, but perhaps I still
miss
> something?

I think that a polynomial time algorithm means that the algorithm's running
time is a polynomial in
 Log(n)/Log(2), not n, because the size of the input matters, not the value
of the number.

Saibal

RE: A little bomb ?

[Bruno Marchal]

Saibal Mitra:

>  > I don't know what the relevance [of PRIMES in P] to quantum computing is.


Doug Donaghue:


>Other than getting primality and factoring confused, I don't knnow either.


BM:

MEA CULPA!  (my fault, my confusion)

And that's nothing compared to my mixing of the bowsprit and the rudder!
   (A thing, as the Bellman remarked
That frequently happens in tropical climes
When a Vessel is so to to speak, "snarked".)

;-)

More seriously I do no more know what exactly is new in that papers 
on the primes.
Here a message I got from friends. I currently agree, but perhaps I still miss
something?


>Is this just a case of sloppy science journalism or (more 
>worryingly) a case of
>an esoteric scientific/mathematical field using terminology in a 
>very misleading way?
>
>The title of the paper by Agrawal et al is: "PRIMES is in P" and reading
>the article you get the impression that this is a new discovery. 
>However, to my knowledge (poor though it is in number theory) 
>checking if a number n is prime or composite can be done in 
>polynomial time by
>simply checking whether any of the numbers up to root n divides n. 
>This takes O(n) divisions and since division is also polynomial then 
>this is
>also a primality testing algorithm that is polynomial.
>
>This confused me for a while. The answer, it seems, is that the 
>authors are talking about
>algorithms that are also practical for numbers of large size with 
>millions of digits.
>The new algorithm has not reclassified the complexity class of a 
>problem as the title and indeed the whole paper (read naively) imply.
>Josh and Max



Bruno