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
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
0.9053732752799988
0 references
0.8285825252532959
0 references
0.7956029772758484
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