Computational complexity of finding the class number Let $f(x)$ be an integral irreducible monic polynomial and $\alpha$ be its root.  What is the computational complexity of finding representatives of ideal classes of the integral ring $\mathbb{Q}[\alpha]$? What is a natural bound for "sizes" of the representatives in terms of the coefficients of $f$? As is explained in Keith  Conrad's notes,  this is related to the conjugacy problem for integral matrices.
 A: I'm not an expert, but this is what I learned from Lenstra's Algorithms in Algebraic Number Theory (Bull AMS, 1992) and Kirschmer and Voight's paper Algorithmic enumeration of ideal classes for quaternion orders:
For a number field $F$ of degree $n$ and absolute discriminant $d_F$, it seems that the best general results about computing the ideal class group comes from Buchmann's 1990 papers A subexponential algorithm for the determination of class groups and regulators of algebraic number fields 
and Complexity of algorithms in algebraic number theory:
One can determine the class group with a deterministic algorithm which runs in time $d_F^{3/4}(2+\log d_F)^{O(n)}$, or in expected run time
$d_F^{1/2}(2+\log d_F)^{O(n)})$ with a probabilistic algorithm.  (Under GRH, one can improve the latter bound for fixed $n$.)  
Edit: Aurel points out in a comment below that an improvement of Schoof gives a deterministic algorithm with runtime $d_F^{1/2}(2+\log d_F)^{O(n)})$, and heuristically it should be computable in subexponential (wrt $\log d_F$) time.
While this does not quite answer your question, it suggests that a natural bound for the "size" is the pair of the degree and discriminant of $F=\mathbb Q(\alpha)$.  Your question of course involves more general orders than the full ring of integers of $F$, and I have not thought about the details, but because one can reduce the class number calculation for $\mathbb Q[\alpha]$ to that for $F$ and the conductor of this suborder, I would expect your problem to be reducible to the class group problem for $F$ in time that is essentially the size of the ring of integers of $F$ modulo the size of your suborder.  (This seems similar to a reduction Kirschmer and Voight do for Eichler orders in quaternion algebras.)
