Maciej Liskiewicz, Rüdiger Reischuk:
The Sublogarithmic Alternating Space World.
Technical report SIIM-TR-A-95-01,
Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck,
1995.
Show postscript | Show abstract
This paper tries to fully characterize the properties and relationships
of space classes defined by Turing machines
that use less than logarithmic space -- may they be deterministic,
nondeterministic or alternating (DTM, NTM or ATM).
We provide several examples of specific languages and show that such machines
are unable to accept these languages.
The basic proof method is a nontrivial extension of the
1^n -> 1^{n+n!} technique to alternating TMs.
Let \llog denote the logarithmic function \log iterated twice,
and Sigma_k Space(S), Pi_k Space (S) be the complexity classes defined
by S-space-bounded ATMs that alternate at most k-1 times and
start in an existential, resp.~universal state.
Our first result shows that for each k > 1 the sets
Sigma_k Space(llog) \ Pi_k Space (o(log)) and
Pi_k Space(llog) \ Sigma_k Space (o(log))
are both not empty. This implies that for each S in the intersection of
Omega(llog) and o(log )
Sigma_1 Space(S), Sigma_2 Space(S), Sigma_3 Space(S) .. ..
form an infinite hierarchy.
Furthermore, this separation is extended to space classes defined
by ATMs with a nonconstant alternation bound A provided that
the product A * S grows sublogarithmically.
These lower bounds can also be used to show that basic closure
properties do not hold for such classes. We obtain
that for any S in Omega(llog) intersection o(log) and all k>1
\Sigma_k Space (S) and \Pi_k Space (S) are not
closed under complementation and concatenation.
Moreover, \Sigma_k Space (S) is not closed under intersection,
and \Pi_k Space (S) is not closed under union.
It is also shown that ATMs recognizing bounded languages can always be
guaranteed to halt. For the class of Z--bounded languages with
Z <= \exp S we obtain the equality
co-Sigma_k Space(S) = Pi_k Space (S) .
Finally, for sublogarithmic bounded ATMs we give a separation between
the weak and strong space measure, and prove a logarithmic lower space
bound for the recognition of nonregular context-free languages.
Key words:
space complexity, sublogarithmic complexity bounds,
alternating Turing machines, halting computations,
complementation of languages,
complexity hierachies, closure properties,
context-free languages, bounded languages.
AMS(MOS) subject classifications: 68Q05, 68Q10, 68Q25, 68Q45
Preliminary versions of these results have been presented at the
10. GI-AFCET Symposium on Theoretical Aspects of Computer Science,
W"urzburg, 1993,
and at the 9. IEEE-SIGACT-EATCS Symposium on Structure in
Complexity Theory, Amsterdam, 1994.
A final version will appear in SIAM Journal on Computing.
