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
      0 references
      15 November 1993
      0 references
      space complexity
      0 references
      complexity classes
      0 references
      alternating Turing machine
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references