  In this paper, we investigate generalizations of the Mahler-Popkens
complexity of integers. Specifically, we generalize to $k$-th roots of unity,
polynomials over the naturals, and the integers mod $m$. In cyclotomic rings,
we establish upper and lower bounds for integer complexity, investigate the
complexity of roots of unity using cyclotomic polynomials, and introduce a
concept of "minimality.'' In polynomials over the naturals, we establish bounds
on the sizes of complexity classes and establish a trivial but useful upper
bound. In the integers mod $m$, we introduce the concepts of "inefficiency'',
"resilience'', and "modified complexity.'' In hopes of improving the upper
bound on the complexity of the most complex element mod $m$, we also use graphs
to visualize complexity in these finite rings.
