We investigate the connections between the complexity of a c.e. set, as calibrated by its strength as an oracle for Turing computations of functions in the Ershov hierarchy, and how strong reducibilities allow us to compute such sets. For example, we prove that a c.e. degree is totally omega-c.e. iff every set in it is weak truth-table reducible to a hypersimple, or ranked set. We also show that a c.e. degree is array computable iff every left-c.e. real of that degree is reducible in a computable Lipschitz way to a random left-c.e. real (a Chaitin's Omega number).