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
Received on Tue Aug 13 2002 - 02:48:38 PDT