Sublogarithmic $\sum _2$-space is not closed under complement and other separation results (Q3142269)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 446228
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Sublogarithmic $\sum _2$-space is not closed under complement and other separation results |
scientific article; zbMATH DE number 446228 |
Statements
Sublogarithmic $\sum _2$-space is not closed under complement and other separation results (English)
0 references
15 November 1993
0 references
space complexity
0 references
complexity classes
0 references
alternating Turing machine
0 references
0 references
0 references
0.9020401835441588
0 references
0.8964691162109375
0 references
0.8875284194946289
0 references
An alternating Turing machine is a two tape non-deterministic Turing machine having a two-way, read-only input tape and a semi-infinite work tape, but whose states have one of two labels -- existential or universal -- attached. The tree of possible computations of such a machine on a given input assigns to each of its nodes the attributes of accept or reject inductively, as follows. (i) Each leaf node is an accept node if it corresponds to an accepting configuration in the usual sense. (ii) Each universal node, all of whose children are accept nodes, is an accept node. (iii) Each existential node, at least one of whose children is an accept node, is an accept node. (iv) All other nodes are reject nodes. An input string is accepted by an alternating Turing machine if the root node of the tree of computations is an accept node. An alternating Turing machine is \(s(n)\) space bounded if on all computations with inputs of length \(n\), no more than \(s(n)\) squares on the work tape are used. The class \(\Sigma_ k\)-SPACE \((s(n))\) is the class of all languages accepted by alternating Turing machines which are \(O(s(n))\) space bounded, which have less than \(k\) alternations between universal and existential states on any accepting computation path, and which have the root state labelled existential. The class \(\Pi_ k\)-SPACE \((s(n))\) is defined similarly, except that the root state is labelled universal. Earlier work cited in this paper established that this alternating space hierarchy collapses for functions \(s(n)>\log (n)\). The present paper establishes separation results for the case when the function \(s(n)\) is between \(\log(n)\) and \(\log\log(n)\), i.e., \(\log\log(n)\leq s(n)\) and \(\sup_{n\to\infty} s(n)/\log(n)= 0\). Specifically, for such \(s(n)\), \[ \Sigma_ 2\text{-SPACE} (s(n))- \Pi_ 2\text{-SPACE} (s(n))\neq\emptyset \] and \[ \Pi_ 2\text{-SPACE} (s(n))- \Sigma_ 2 \text{-SPACE} (s(n))\neq \emptyset. \] As a corollary one gets \[ \Sigma_ 1\text{-SPACE} (s(n))\subset \Sigma_ 2\text{-SPACE} (s(n))\subset \Sigma_ 3\text{-SPACE} (s(n)) \] and \[ \Pi_ 1\text{- SPACE} (s(n))\subset \Pi_ 2\text{-SPACE} (s(n))\subset \Pi_ 3\text{- SPACE} (s(n)), \] where the inclusions are strict. The arguments involve careful analysis of the computations of alternating Turing machines.
0 references