# String transformer : Polynomial time approximation schemes?

A program P takes a string as an input and returns a string of same length as output.

Q Given two strings A and B how fast can a program tell weather string B cannot be obtained by a recursive application of P over the initial string A ?

Q Given P , length L of the strings and the initial string A how fast can a program find the number of L symbol strings which can not be obtained through any finite number of iterations through P of the initial string A ?

The above appear to be the type NP hard problems are; can these be proved as NP hard ; what I am interested in schemes which solve them efficiently i.e. have polynomial time complexity.

• You don't say that $P$ itself is polynomial time computable, but do you intend that? – Joel David Hamkins Sep 13 '13 at 13:58
• Yes P is polynomial time computable. – ARi Sep 13 '13 at 14:00
• – Benjamin Steinberg Sep 13 '13 at 17:50
• – Kaveh Sep 24 '13 at 16:30

Theorem. There is $P$ for which the reachability problem in your first question is NP hard.

Proof. Suppose we have any NP decision problem $A$, where for any string $a$, we have $a\in A$ if and only if there is a string $b$ of the same length such that a fixed polynomial time program $p$ accepts $(a,b)$ (this form is achievable without loss of generality by padding). Consider now the following algorithm $P$. On strings of the form $(a,x)$, where $x$ has the same length a $a$, our algorithm checks if $p$ accepts $(a,x)$, and if so, outputs a default accepting output. Otherwise, our algorithm outputs $(a,x^+)$, where $x^+$ is the lexicographic successor to $x$ in the space of all strings of that length, unless $x$ was already the lexically maximal string of that length, in which case $P$ outputs a default rejecting output. This program is polynomial time computable, since it takes just a little longer than $p$ does. But notice that iterating $P$ has the effect of searching through the exponential-size space of witnesses. In particular, if $\vec 0$ is the lexically least string, then $(a,\vec 0)$ reaches the default accepting output if and only if there is a witness for $a$, if and only if $a\in A$. So we have reduced $A$ to your problem for this $P$, and so if $A$ is NP-complete, your problem is NP hard. QED

Meanwhile, I don't expect that your problem is always in NP itself, since it seems that one can use exponential size iterations, in the way I just did, and I don't see how to have a polynomial size witness to reachability. (Meanwhile, the reachability problem for some other $P$ can of course be trivial.)

A similar idea shows more:

Theorem. There are $P$ for which your reachability problem is PSPACE complete.

Proof. First, let's show that it can be PSPACE hard. Given any program $p$, such that $p(a)$ runs in polynomial space, design a program $P$ to computer from input of the form $(a,c)$, where $c$ is a string that will be regarded as encoding the configuration during the computation of $p(a)$, of the right length for the bounded on the space needed by $p(a)$. Our program $P$ will perform one step of the computation of $p(a)$ by moving $c$ to the next configuration $c^+$ that would arise during the computation of $p$, or a default accepting or rejecting string if $p(a)$ should halt right at this step of computation. Thus, iterating $P$ corresponds to undertaking the computation of $p(a)$. Therefore, we can reduce the question about whether $p$ accepts or rejects $a$ to the question of whether a certain string is reachable from $(a,c_0)$, where $c_0$ is the starting configuration for $p(a)$. So every PSPACE decidable question reduces to one of your reachability decision problems, and so by using a PSPACE complete $p$, we see that one of your decision problems is PSPACE hard.

Finally, we show that all your reachability problems are themselves in PSPACE. To see if $B$ is reachable from $A$ via $P$, we simply compute successive iterates $P^k(A)$, while at the same time incrementing a counter to count up to the total number of strings of that length (as in the NP argument above). We can do this in polynomial space. If we find that $B$ is reached, then we accept. If the counter runs out and we did not reach $B$, then since we iterated long enough, we know $B$ is not reachable and so we may confidently reject.

So we have PSPACE completeness. QED

• It might be good to mention that the assumption in the first sentence that $b$ has the same length as $a$ is no loss of generality, since it can be achieved by padding. – Andreas Blass Sep 13 '13 at 14:20
• It might be worth to mention that the problem is PSPACE-complete, not just hard. – Emil Jeřábek Sep 13 '13 at 15:32
• I clarified the situation that one has a different decision problem for each $P$. For any given $P$, we have the reachability problem that accepts or rejects strings $(A,B)$ of the same length, depending on whether $B=P^k(A)$ for some $k$. – Joel David Hamkins Sep 13 '13 at 20:15
• Since the problem is PSPACE complete, we should not be expecting any efficient algorithms. The fastest algorithm I can see is the brute-force algorithm to compute all the iterations of $P$, and this takes exponential time. – Joel David Hamkins Sep 24 '13 at 14:12
• @Kaveh, In the comments, the OP says that P is polytime computable. – Joel David Hamkins Sep 24 '13 at 16:18