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,](http://www.math.uconn.edu/~kconrad/blurbs/gradnumthy/matrixconj.pdf) this is related to the conjugacy problem for integral matrices.



Computational complexity of finding the class number
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.)


