  The group of automorphisms of the Cuntz algebra $\mathcal{O}_{2}$ is a Polish
group with respect to the topology of pointwise convergence in norm. Our main
result is that the relations of conjugacy and cocycle conjugacy of
automorphisms of $\mathcal{O}_{2}$ are complete analytic sets and, in
particular, not Borel. Moreover, we show that from the point of view of Borel
complexity theory, classifying automorphisms of $\mathcal{O}_{2}$ up to
conjugacy or cocycle conjugacy is strictly more difficult than classifying up
to isomorphism any class of countable structures with Borel isomorphism
relation. In fact the same conclusions hold even if one only considers
automorphisms of $\mathcal{O}_{2}$ of a fixed finite order. In the course of
the proof we will show that the relation of isomorphism of Kichberg algebras
(with trivial $K_{1}$-group and satisfying the Universal Coefficient Theorem)
is a complete anaytic set. Moreover, it is strictly more difficult to classify
Kirchberg algebras (with trivial $K_{1}$-group and satisfying the Universal
Coefficient Theorem) than classifying up to isomorphism any class of countable
structures with Borel isomorphism relation.
