Complexity of Pythagorean triples
This is not a full answer, but I think it is very useful.

Euclid's formula generates all primitive triples in a fairly linear fashion. Using all integers $m, n$ with $m &gt; n$, $m, n$ coprime and $m-n$ is odd, all primitive triples can be generated as

$$a=m^2-n^2, b=2mn, c=m^2 + n^2$$

I don't have any knowledge on complexity, but hopefully this will help