5
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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? $\endgroup$ – usul Sep 24 '13 at 15:09
  • $\begingroup$ Wouldnt the program P itself count ie does the analysis of the program have any bearing? $\endgroup$ – ARi Sep 24 '13 at 15:13
  • $\begingroup$ Thanks for pointing out APX hardness though $\endgroup$ – ARi Sep 24 '13 at 15:22
  • $\begingroup$ 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? $\endgroup$ – Kaveh Sep 24 '13 at 16:54
  • $\begingroup$ Yes It is the same Program P ; The edit is OK now $\endgroup$ – ARi Sep 24 '13 at 16:55
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – ARi Sep 27 '13 at 16:41
  • $\begingroup$ @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. $\endgroup$ – Sasho Nikolov Sep 27 '13 at 16:44

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.