<p>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.</p>

<p>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$. </p>

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

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

<p>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.</p>

CC BY-SA 3.0
2013-09-27T16:41:00.587Z
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
CC BY-SA 3.0
2013-09-27T16:44:37.810Z
@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
CC BY-SA 3.0
2013-09-25T01:13:28.220Z
2013-09-25T13:24:22.343Z
2013-09-25T13:24:22.343Z
Sasho Nikolov
<p>Let $P$ be a length-preserving (i.e. $|P(x)|=|x|$) 
polynomial-time computable program.</p>

<p>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$?</p>

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

<p>I am looking for <a href="http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme" rel="nofollow noreferrer">PTAS</a> algorithms for these problems.</p>

<hr>

<p>The first problem is PSpace-complete, see <a href="https://mathoverflow.net/a/142064/">this answer</a> on MO.</p>

CC BY-SA 3.0
2013-09-24T15:09:59.483Z
I think if your problem is PSPACE-complete (according to the link), then in particular it is [APX](http://en.wikipedia.org/wiki/APX)-hard, so there should not be a PTAS. Does that sound right?
usul
CC BY-SA 3.0
2013-09-24T15:13:23.520Z
Wouldnt the program P itself count ie does the analysis of the program have any bearing?
ARi
CC BY-SA 3.0
2013-09-24T15:22:21.790Z
Thanks for pointing out APX hardness  though
ARi
CC BY-SA 3.0
2013-09-24T16:54:22.877Z
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
CC BY-SA 3.0
2013-09-24T16:55:35.510Z
Yes It is the same Program P ; The edit is OK now
ARi
CC BY-SA 3.0
2013-09-25T00:23:14.577Z
Can you clarify what it means to have a PTAS for problem 1? A PTAS makes sense for optimization or counting problems, but problem 1 is a decision problem.
Sasho Nikolov
CC BY-SA 3.0
2013-09-25T03:35:31.763Z
PTAS is applicable  only for problem II
ARi
<cc.complexity-theory><ds.algorithms><np-hardness><polynomial-time>
A reachability problem
ARi
# A reachability problem

(Asked by: username_0 on 2013-09-24)

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](http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme) algorithms for these problems.

---

The first problem is PSpace-complete, see [this answer](https://mathoverflow.net/a/142064/) on MO.

**Tags:** cc.complexity-theory, ds.algorithms, np-hardness, polynomial-time
> **Comments:**
> **username_1**: I think if your problem is PSPACE-complete (according to the link), then in particular it is [APX](http://en.wikipedia.org/wiki/APX)-hard, so there should not be a PTAS. Does that sound right?  
> **username_0**: Wouldnt the program P itself count ie does the analysis of the program have any bearing?  
> **username_0**: Thanks for pointing out APX hardness  though  
> **username_2**: 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?  
> **username_0**: Yes It is the same Program P ; The edit is OK now  
> **username_3**: Can you clarify what it means to have a PTAS for problem 1? A PTAS makes sense for optimization or counting problems, but problem 1 is a decision problem.  
> **username_0**: PTAS is applicable  only for problem II  

---

## 1 answers

### Answer by username_3 on 2013-09-25. Score: 11 | Accepted answer

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.

> **Comments:**
> **username_0**: 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  
> **username_3**: @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.  

---

