IMMERMAN-SZELEPCSéNYI THEOREM

The 'Immerman-Szelepcsényi Theorem' was proven independently by Neil Immerman and Róbert Szelepcsényi in 1987, for which they shared the 1995 Gödel Prize. In its general form the theorem states that NSPACE = co-NSPACE. In other words, if a nondeterministic machine can solve a problem, it can solve its complement problem (with the ''yes'' and ''no'' answers reversed) in the same asymptotic amount of space. No similar result is known for time.

Contents

Proof

References

Proof

Let ''s(n)'' ≥ log n be a space constructible function. Then ''NSPACE[s(n)]=co-NSPACE[s(n)]''
The first step is to demonstrate that NL=co-NL. This can be accomplished by taking the st-connectivity
problem (known to be NL-complete), and showing that the
complement of this problem (called st-non-connectivity) is also in
NL.

'Definition:' st-non-connectivity is an algorithm
on graph ''G'' with ''n'' vertices that outputs "TRUE" if there is no
path between vertex ''s'' and ''t'' and "FALSE" if at least one path exists.
st-non-connectivity={ <''G=,s,t''>: there is no path from ''s'' to ''t'' in graph ''G''}.
In order to illustrate that st-non-connectivity is in NL, one can construct an algorithm that, in logarithmic space, decides whether two given vertices are
not connected.
First, define ''A_i'' as follows:
''A_i''={ ''v'' : there is a path from ''s'' to ''v'' of length ≤ ''i'' }. In other words, ''A_i'' will include all vertices that are reachable from ''s'' in ''i'' or
fewer hops. Let ''r_i'' =| ''A_i'' |. Note that if
''t'' is not in ''A_n-1'', where ''n'' =| ''V'' |, then there is no path from ''s'' to ''t'' in ''G'', ''i.e.'' <''G,s,t''> ∈ st-non-connectivity.
'Lemma': An algorithm can be constructed that given ''r_i'' will enumerate vertices in ''A_i'' and ACCEPT in logarithmic space. Note that if the given ''r_i'' is larger than the true number of vertices in ''A_i'', then the algorithm REJECTs; however, if ''r_i'' is less than the true number of vertices in ''A_i'' the algorithm would ACCEPT but enumerate only a subset of ''A_i''.
ENUMERATE(s,i,r_i,G)
1: Counter:=0
2: FOR ALL vertices v in G
3: Nondeterministically guess a path of length less than or equal to i from s to v
4: IF path exists
5: Counter:=Counter+1
6: Output v
6: IF Counter>=r_i
7: ACCEPT
8: ELSE
9: REJECT
ENUMERATE goes through all vertices of graph ''G'' in logarithmic
space, since the representation of each vertex and the 'Counter' requires
only log | ''G'' | bits and nondeterministically selecting a path also
requires only logarithmic space.
Now, with ENUMERATE at hand it is possible to compute the actual ''r_i'' in log-space using an algorithm that is based on the principle of Mathematical induction.
Obviously ''r₀''=1 since ''A_i'' includes only the vertex ''s'' itself.
Now, assume ''r_i'' is given. Then ''r_i+1'' = | ''A_i+1'' ''A_i'' | + ''r_i'' , where is the set difference operator. The set difference can be calculated by the following algorithm in log-space:
SET-DIFFERENCE (s,i,r_i,G)
1: diff:=0
2: FOR ALL vertices v:
3: ENUMERATE (s,i,r_i,G)
4: IF v is ever outputted
5: CONTINUE
6: FOR EACH u such that (u,v) is an edge in G
7: ENUMERATE (s,i,r_i,G)
8: IF u is ever outputted
9: diff:=diff+1
10: ELSE
11: CONTINUE
12:Output diff
This algorithm goes through all vertices of the graph ''G'' and ignores the vertices that are of distance of less than or equal to ''r_i'' from ''s'' (lines 4-5), ''i.e.'' the vertices included in ''A_i''. In lines 6-9 the algorithm tries to find a vertex ''u'' in ''A_i'' directly connected to the vertex ''v'' outside of ''A_i'' by simulating ENUMERATE again. If such vertex is found, that means that ''v'' is not in ''A_i'' but is in ''A_i+1'', so it is outputted and the number of vertices in set difference is recorded. Note that the algorithm does not need to store all of the output of ENUMERATE every time it is called as a sub-routine. In lines 3 and 7 it can only store one vertex at a time and check if ''v'' and ''u'' are ever outputted. Thus, this algorithm runs in logarithmic space.
With this algorithm at hand we can devise an algorithm for st-non-connectivity consisting of two parts. The first part would compute ''r_n'' by starting with ''r₀''=1 and then using SET-DIFFERENCE n-1 times. In the second part the algorithm just simulates ENUMERATE with the computed ''r_n'' and if ''t'' is ever outputted that means it can be reached from ''v'', and the algorithm REJECTS.
NOT-CONNECTED (G,s,t)
1: r_n:=1;
2: FOR i:=1 TO n
3: r_n:=r_n+SET-DIFFERENCE (s,i,r_n,G)
4: ENUMERATE (s,n,r_n,G)
5: IF t is ever outputted
6: REJECT
8: ELSE
9: ACCEPT
This algorithm runs in logarithmic space, since we need log | ''G'' |
bits for storing ''i and r_n''. As
was shown above, the ENUMERATE and SET-DIFFERENCE algorithms also run in logarithmic
space and again we do not need to store all of the output of ENUMERATE in line 4, but need only to check if ''t'' is ever outputted. Thus, NOT-CONNECTED can decide if there exists no path from
vertex ''s'' to ''t'' in logarithmic space. I.e. st-non-connectivity
is in NL. Since we can reduce each problem in NL to st-connectivity and each problem in co-NL to st-non-connectivity we conclude
that NL=co-NL.
Now, for ''s(n)'' ≥ log n we can transform the computations of any
non-deterministic Turing Machine ''M'' on language ''L'' into a graph of its states
and simulate ''M'' using st-connectivity algorithm. Analogously we can
transform any ''co-language'' into st-non-connectivity problem.
Both of these graphs would have 2^''O(s(n))'' vertices if ''L'' ∈
''NSPACE(s(n))''. Thus, we can decide both reachability and
non-reachability of the ''Accept'' state in log(2^''O(s(n))'')=''O(s(n))'' space and ''NSPACE(s(n))=co-NSPACE(s(n))''.

References

★ N.Immerman, "'''Nondeterministic Space is Closed Under Complement'''", SIAM J. Comput. 17 1988, pp. 935-938

★ R.Szelepcsenyi, "'''The method of forcing for nondeterministic automata'''", Bull. EATCS 33, 1987, pp. 96-100