# 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.

• I think if your problem is PSPACE-complete (according to the link), then in particular it is APX-hard, so there should not be a PTAS. Does that sound right? – usul Sep 24 '13 at 15:09
• Wouldnt the program P itself count ie does the analysis of the program have any bearing? – ARi Sep 24 '13 at 15:13
• Thanks for pointing out APX hardness though – ARi Sep 24 '13 at 15:22
• I am guessing that $P$ in the second problem also satisfies the conditions, (length-preserving, polynomial-time computable). Also, do you want to be fixed like the first problem or be part of the input? – Kaveh Sep 24 '13 at 16:54
• Yes It is the same Program P ; The edit is OK now – ARi Sep 24 '13 at 16:55

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.

• If I could choose an oracle to help me out (as obviously for even a moderate length string my chances of getting an answer in a lifetime are nil).. which would be the weakest / least complex one; just so I can get some approximate value for my function ( number of unreachable strings) in "less" time?.Of course we do not talk of the "reachability Oracle" here, but say if I could use the Boolean SAT oracle. – So now I talk of PTAS with oracle of the least complexity class – ARi Sep 27 '13 at 16:41
• @ARi that sounds something that is better as a new question. and if you want to post it as a new question it might be helpful to specify what oracles you consider acceptable. i do not even see a way to use something like "is string $y$ reachable from string $x$" to answer problem II. – Sasho Nikolov Sep 27 '13 at 16:44