I was wondering if there are any known (upper and lower) bounds for the complexity of computing the class-number of a finite extension of the rationals. (A general bound should be in function of the discriminant, I guess.)


This would also be of interest in special cases like fields with a given degree or signature. The simplest one would be the family of imaginary quadratic fields: in this setting there is [Swan's algorithm](http://www.ams.org/mathscinet-getitem?mr=284516) (which actually computes reduced bases for all ideals of least norms in their class), which takes (I think) at most $m^3$ steps to do $\mathbb{Q}(\sqrt{-m})$ when implemented without more thought. Is there a better algorithm known, or is there a speedy implementation of Swan's algorithm? 



How long does it take to compute a class number?
In the case of quadratic fields there is a very nice paper of Andy Booker (see <http://www.ams.org/journals/mcom/2006-75-255/S0025-5718-06-01850-3/home.html> ) which uses the Burgess bounds on character sums (among other ideas) to compute the class number. The running time is always $O(D^{1/2+\epsilon})$ and if the GRH is true then the algorithm executes in time $O(D^{1/4+\epsilon})$. I think this is the best that is known. If one wants all class numbers up to a point then there are other clever algorithms based on the trace formula for doing this (see work of Jacobson, Ramachandran and Williams; Springer Lecture notes in CS vol 4076). 


Note: As Edgardo observes there are faster randomized algorithms, and also earlier algorithms that rely on GRH (either running in heuristically subexponential time, or in time $D^{1/4+\epsilon}$). But these use GRH in an essential way in that the algorithm halts only if GRH is true. A subtle difference in Booker's algorithm is that it is guaranteed to halt; only the analysis of how long it takes to halt depends on GRH. 


