<p>The nondeterministic polynomial-space algorithm for this problem works as follows:</p>

<ol>
<li>Initialize <i>h</i>: <i>A</i>→<i>A</i> to the identity mapping.</li>
<li>Is <i>h</i>=<i>g</i>?  If so, we found out that <i>g</i> is in the monoid generated by <i>S</i>; accept and halt.</li>
<li>Guess one element <i>f</i>∈<i>S</i>.</li>
<li>Update <i>h</i> to <i>f</i>∘<i>h</i>.</li>
<li>Go to step 2.</li>
</ol>

<p>As you correctly pointed out, the sequence can be exponentially long in the input size, so this algorithm may take exponential time before accepting.</p>

<p>Note that the algorithm does not guess a whole sequence at once and store this sequence in the work space—doing so would require exponential space.</p>

CC BY-SA 3.0
2012-08-19T20:08:16.903Z
2012-08-19T22:01:31.743Z
2012-08-19T22:01:31.743Z
Tsuyoshi Ito
<p>"Given a finite set $A$, a set of functions $S=\left\{f_{1}, f_{2}, \ldots, f_{k}\right\}$, each $A \to A$, and a candidate function $g:A \to A$, is $g$ in the monoid generated by $S$ with respect to composition?"</p>

<p>Kozen's paper "<a href="http://www.cs.cornell.edu/~kozen/papers/LowerBounds.pdf" rel="nofollow">Lower bounds for natural proof systems</a>" shows that this problem is PSPACE-complete. The following question is about his argument that the problem is in PSPACE.</p>

<p>He argues that it is easy to compute function composition if we represent the functions as bipartite graphs. Now we just guess a sequence of $f_{i}$s, compose them, and check whether it equals $g$. Thus, it can be done in nondeterministic linear space, and by Savitch's theorem, the problem is in PSPACE.</p>

<p>But is this really sufficient to see that the problem is in nondeterministic linear space? The representation of $g$ using terms from $S$ might itself be exponentially long. The paper concedes this just before definition 3.2.2, and is an otherwise interesting little fact about permutations (which are a special case of the system being considered) -- the order of a permutation over $n$ elements may be exponentially large in $n$ (See <a href="http://en.wikipedia.org/wiki/Landau%27s_function" rel="nofollow">this</a>).</p>

CC BY-SA 3.0
2012-08-19T14:43:46.283Z
I think that the claim is correct.  Why do you have to store the representation of g as the product of elements in S?  You only have to decide whether such a representation exists or not.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-19T19:30:13.467Z
The certificate that $g$ is an element of the monoid generated by $S$ is what would be exponentially long in the input size. You're right -- we don't need to output this certificate, but the nondeterministic algorithm needs it.
Anonymous
CC BY-SA 3.0
2012-08-19T19:31:47.023Z
No, a nondeterministic algorithm does not have to store the whole certificate string in its work space.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-19T19:39:27.307Z
Oops! Sorry, my mistake. You (and the paper) are right. Don't know what I was thinking.
Anonymous
<co.combinatorics>
Membership testing in transformation monoids
Anonymous
# Membership testing in transformation monoids

(Asked by: username_0 on 2012-08-19)

"Given a finite set $A$, a set of functions $S=\left\{f\_{1}, f\_{2}, \ldots, f\_{k}\right\}$, each $A \to A$, and a candidate function $g:A \to A$, is $g$ in the monoid generated by $S$ with respect to composition?"

Kozen's paper "[Lower bounds for natural proof systems](http://www.cs.cornell.edu/~kozen/papers/LowerBounds.pdf)" shows that this problem is PSPACE-complete. The following question is about his argument that the problem is in PSPACE.

He argues that it is easy to compute function composition if we represent the functions as bipartite graphs. Now we just guess a sequence of $f\_{i}$s, compose them, and check whether it equals $g$. Thus, it can be done in nondeterministic linear space, and by Savitch's theorem, the problem is in PSPACE.

But is this really sufficient to see that the problem is in nondeterministic linear space? The representation of $g$ using terms from $S$ might itself be exponentially long. The paper concedes this just before definition 3.2.2, and is an otherwise interesting little fact about permutations (which are a special case of the system being considered) -- the order of a permutation over $n$ elements may be exponentially large in $n$ (See [this](http://en.wikipedia.org/wiki/Landau%27s_function)).

**Tags:** co.combinatorics
> **Comments:**
> **username_1**: I think that the claim is correct.  Why do you have to store the representation of g as the product of elements in S?  You only have to decide whether such a representation exists or not.  
> **username_0**: The certificate that $g$ is an element of the monoid generated by $S$ is what would be exponentially long in the input size. You're right -- we don't need to output this certificate, but the nondeterministic algorithm needs it.  
> **username_1**: No, a nondeterministic algorithm does not have to store the whole certificate string in its work space.  
> **username_0**: Oops! Sorry, my mistake. You (and the paper) are right. Don't know what I was thinking.  

---

## 1 answers

### Answer by username_1 on 2012-08-19. Score: 5 | Accepted answer

The nondeterministic polynomial-space algorithm for this problem works as follows:

1. Initialize *h*: *A*→*A* to the identity mapping.
2. Is *h*=*g*? If so, we found out that *g* is in the monoid generated by *S*; accept and halt.
3. Guess one element *f*∈*S*.
4. Update *h* to *f*∘*h*.
5. Go to step 2.

As you correctly pointed out, the sequence can be exponentially long in the input size, so this algorithm may take exponential time before accepting.

Note that the algorithm does not guess a whole sequence at once and store this sequence in the work space—doing so would require exponential space.


---

