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 ∈ T 2 , saddles of common period n , and rational r > 0 sufficiently small, we study how quickly orbits ( f n ) 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 ( f n ) 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 . [ABSTRACT FROM AUTHOR]