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 ?

[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