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