Nondeterministic Computations in Sublogarithmic Space and Space Constructibility (Q3978779)

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 12899
Language Label Description Also known as
default for all languages
No label defined
    English
    Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
    scientific article; zbMATH DE number 12899

      Statements

      Nondeterministic Computations in Sublogarithmic Space and Space Constructibility (English)
      0 references
      0 references
      25 June 1992
      0 references
      space-bounded computation
      0 references
      space constructibility
      0 references
      nondeterministic space
      0 references
      reversing automaton
      0 references
      sublogarithmic space
      0 references
      nondeterministic Turing machine
      0 references
      Call a function \(s(n)\) nondeterministically fully space constructible if it can be computed by a nondeterministic Turing machine having a read- only input tape and a read-write scratch tape in such a way that for each \(n\) the space used on the scratch tape while computing \(s(n)\) is bounded by \(s(n)\). This bound holds for all computation paths and is attained for at least one. The main result of the paper is that there exists no monotone increasing fully space constructible function \(s(n)\) such that \(\sup_{n\to \infty}{s(n)\over\log n}=0\). The proof uses a careful analysis of computations of such Turing machines using, in particular, the notion of a ``\(U\)-turn'' - a computation that takes the machine from one configuration to another such that the two configurations differ only with regard to the position of the head on the input tape. Consequences of the result are the facts that \(\log\log(n)\) and \(\sqrt{\log(n)}\) are not nondeterministically fully space constructible and that various languages are not recognizable in sublogarithmic space. The paper concludes by summarizing a number of containment relations between space complexity classes which are implied by the main result.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references