# Understanding why ALL_nfa is in co-nspace

I'm trying to understand Sipser's example showing that $ALL_{nfa} \in Co-NSPACE(n)$, where $$ALL_{nfa} = \{ <A> | A \text{ is an NFA such that } L(A) = \Sigma^*\}.$$

The algorithm can be seen here.

I'm confused by a few things, but mainly what is meant by "nondeterministically select an input symbol"? If I "nondeterministically" choose symbol 'a' and then mark all the vertices I can reach from the current ones by 'a', then don't I possibly miss out on the vertices reachable by 'b'? And even though we repeat this $2^q$ times, what's to stop me from choosing that 'a' transition each time?

If my instincts are correct, then what we are trying to do is convert the nfa to a dfa (which will have at most $2^q$ states). If the dfa has a single reject state, then we know the nfa has a string that will be rejected. However, we would like to do this without actually converting to a dfa, which might require too much space. So the provided algorithm tries to traverse the corresponding dfa graph, without actually building it?

## 1 Answer

To show that $ALL_{\mathsf{NFA}}$ is in $\mathrm{co-NSPACE}(n)$, we must show that the complement $\overline{ALL_{\mathsf{NFA}}}$ is in $\mathrm{NSPACE}(n)$.

The complement is

$$\overline{ALL_{\mathsf{NFA}}} = \{ \langle N \rangle \mid N \text{ is an NFA where } L(N) \neq \Sigma^* \}$$

To show that $\overline{ALL_{\mathsf{NFA}}}$ is in $\mathrm{NSPACE}(n)$ we therefore need to devise a Turing machine that, given an NFA description $\langle N \rangle$ can tell us if there exists an input that $N$ will not accept.

Essentially, the machine will nondeterministically guess a string $w$ and verify that this string is not accepted by $N$. Our machine may guess the wrong string, but remember that the machine is nondeterministic -- as long as it is possible to guess a string with this property, the machine will accept $\langle N \rangle$.

To guess such a string $w$ and check that the NFA does not accept it, we need to explore all the possible computations of $N$ on $w$ and show that none of them will lead to an accepting state. This does not require us to construct an equivalent DFA using the subset construction; doing this would require more than linear space. However, even just storing all of the computations of $N$ on $w$ on the Turing machine tape will require more than $n$ tape cells.

The trick is to guess the string symbol by symbol and keep track of the sets of states that $N$ could possibly be in after it has read a symbol. If $N$ has $q$ states, there are $2^q$ such sets of possible states. We start with the set $\{ q_0 \}$ and guess a sequence of $2^q$ symbols. For each symbol that we guess, we record the subset of states that can be visited from any of the states that $N$ could be in now. We can keep track of this subset of possible current states using $q$ bits (represented as $q$ cells on the tape). This is linear in $n$ where $n$ is the length of $\langle N \rangle$. This description must at the very least list the states of $N$, so $q = O(n)$.

If the set of possible current states that we are now in does not contain an accept state, then we have found a string that cannot be accepted by $N$. We may have to guess $2^q$ symbols, since each symbol could in principle lead us to a new set of possible current states that had not been seen before. But once all sets of possible current states have been examined, we can stop. We can count to $2^q$ in binary using no more than $q$ bits. Again this requires no more than $O(n)$ bits.

• Nice explanation! Perhaps it's also worth briefly mentioning why the NFA state transitions cannot be guessed and have to be all simulated, as this is a usual point of confusion with this proof. – aelguindy Nov 1 '16 at 22:32
• See the part of my answer that begins with "To guess such a string..." – Hans Hüttel Nov 1 '16 at 22:39
• Yes I am not saying you did not mention that all paths need to be checked. I am saying that a confused reader might wonder why not use non-determinism to check a single path. Not pointing errors in your answer, just suggesting an improvement :). – aelguindy Nov 1 '16 at 22:46
• I'm still missing a main point somewhere... I understand that we can check all the possible computations of $N$ on $w$ by doing a sort of breadth first search using $w$ as our guide. What I'm still blocking on is the "nondeterministic guess" of $w$. If we guess the string "aaabbb....." and check all possible computations on it, couldn't we miss out on the results of trying something like "bbbaaa....? – theQman Nov 1 '16 at 22:53
• @theQman. To make life simple, let's say the alphabet is $\{a,b\}$. Then our machine will guess that the first symbol of $w$ is $a$ and (in another universe, if you like) will also guess that the first symbol is $b$. Continue this "cloning of universes" for the second symbol, the third, and so on. That's how nondeterminism works: if there's any universe in which $N$ doesn't accept its particular version of the input, we've found what we needed. – Rick Decker Nov 1 '16 at 23:12