A reachability problem Let $P$ be a length-preserving (i.e. $|P(x)|=|x|$) 
polynomial-time computable program.

I. 
Given two strings $x$ and $y$, 
we want to decide if $y$ can be obtained by 
repeated applications of $P$ to $x$. 
In other words,
is there a $k$ such that $P^k(x)=y$?

II. Given a string $x$,
find the number strings of length $|x|$ 
which cannot be obtained by repeated applications of $P$ to $x$?

I am looking for PTAS algorithms for these problems.



The first problem is PSpace-complete, see this answer on MO.
With respect to Problem II, it is coNP-hard (under Karp reductions) to tell if the number of unreachable strings is 0 or at least $1 - 2^{-\text{poly}(|x|)}$ fraction of all strings. I suspect there is a way to boost this and show that the gap problem is PSPACE-hard, maybe by using IP as a robust characterization of PSPACE.

Let $L$ be a coNP-complete language. There exists a polynomial time Turing machine $M$ and a polynomial $p$ such that $x \in L$ if and only if for all $w$, $|w| = p(|x|)$, we have $M(x, w) = 0$. 

Construct $P$ to be the following program. It takes $z$ where $|z| = p(|x|) + i$ and maps it to 


itself if $z = (w, 0^{i})$ and $M(x, w) = 1$
to $z'$, where $z'$ is the successor of $z$ in the lexicographic order, otherwise


Notice that if $x \in L$, then starting from $0^{p(|x|) + i}$ and repeatedly applying $P$ we run through all strings $z$ of size $p(|x|) + i$. Otherwise, there is some $w$ such that $M(x, w) = 1$ and the repeated applications of $P$ reach at most $2^{p(|x|)}$ strings. Taking $i$ to be a large enough polynomial in $|x|$ finishes the proof.