Re: A little bomb ?

From: Bruno Marchal <>
Date: Tue, 13 Aug 2002 11:42:01 +0200

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 (**)).


Received on Tue Aug 13 2002 - 02:48:38 PDT

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:07 PST