2
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Andreas Blass Sep 13 '13 at 14:20
  • $\begingroup$ It might be worth to mention that the problem is PSPACE-complete, not just hard. $\endgroup$ – Emil Jeřábek Sep 13 '13 at 15:32
  • 1
    $\begingroup$ 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$. $\endgroup$ – Joel David Hamkins Sep 13 '13 at 20:15
  • 1
    $\begingroup$ 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. $\endgroup$ – Joel David Hamkins Sep 24 '13 at 14:12
  • 1
    $\begingroup$ @Kaveh, In the comments, the OP says that P is polytime computable. $\endgroup$ – Joel David Hamkins Sep 24 '13 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.