On the complexity of Anosov saddle transitions

We study the computational complexity of some problems which arise in the dynamics of certain hyperbolic toral automorphisms, using the shadowing lemma. Given p,q∈T2, saddles of common period n, and rational r>0 sufficiently small, we study how quickly orbits (fn)N(z) ​transit from a basin of p, the open ball B(p,r) to one of q, B(q,r). A priori, z is of arbitrary precision. We compute a finite precision L, polynomial in the size of an instance, so that if an orbit (fn)N(z) makes such a transition, so does a reliable L-precision pseudo-orbit, but at the price of possibly using duration N+1. If we allow duration N+2, this precision depends on n and r but is independent of N. It follows that in an appropriate model of computation such a saddle transition problem is in Oracle NP i.e. in NP up to a restricted oracle, and we show there exist closely related problems which are in NP.