We study the problem of computing stationary Nash equilibria in discounted perfect information stochastic games from the viewpoint of computational complexity. For two-player games we prove the problem to be in \(\textrm{PPAD}\) , which together with a previous \(\textrm{PPAD}\) -hardness result precisely classifies the problem as \(\textrm{PPAD}\) -complete. In addition to we give an improved and simpler \(\textrm{PPAD}\) -hardness proof for computing a stationary \(\varepsilon \) -Nash equilibrium. For 3-player games we construct games showing that rational-valued stationary Nash equilibria are not guaranteed to exist, and we use these to prove \(\textsc {SqrtSum} \) -hardness of computing a stationary Nash equilibrium in 4-player games.