Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
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.
- A communication hierarchy of parallel computations
- On space functions constructed by two-dimensional Turing machines
- A relationship between nondeterministic turing machines and 1-inkdot turing machines with small space
- Bridging across the (n) space frontier
- On 1-inkdot alternating Turing machines with small space
- A note on multi-inkdot nondeterministic Turing machines with small space
- On space functions fully constructed by two-dimensional Turing machines
- Space hierarchy theorem revised.
- Converting two-way nondeterministic unary automata into simpler automata.
- Oblivious two-way finite automata: decidability and complexity
- Magic numbers in the state hierarchy of finite automata
- A space lower bound for acceptance by one-way _2-alternating machines
- Weak and strong one-way space complexity classes
- Translation from classical two-way automata to pebble two-way automata
- Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
- scientific article; zbMATH DE number 3856412 (Why is no real title available?)
- On the State Complexity of Operations on Two-Way Finite Automata
- Factoring and Testing Primes in Small Space
- scientific article; zbMATH DE number 4045156 (Why is no real title available?)
- Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties
- Nondeterministic computations in sublogarithmic space and space constructibility
- Sublogarithmic Bounds on Space and Reversals
- A hierarchy that does not collapse : alternations in low level space
- An alternating hierarchy for finite automata
- On languages accepted with simultaneous complexity bounds and their ranking problem
- Investigations on automata and languages over a unary alphabet
- Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\)
- Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\)
- Two-way automata and bounded languages
- If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n
This page was built for publication: Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3978779)
