Iirc, there's a big difference between the computational complexity of what a transformer can solve and what it can solve in practice; what it can solve in practice tends to come from things like singular learning theory (which describes the forms of generalizations that a given ML algorithm can make), but I think (iirc) that transformers can compute a pretty broad class of O(N^2) functions?