Remarks on languages acceptable in log log n space (Q1107318)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Remarks on languages acceptable in log log n space |
scientific article; zbMATH DE number 4064486
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Remarks on languages acceptable in log log n space |
scientific article; zbMATH DE number 4064486 |
Statements
Remarks on languages acceptable in log log n space (English)
0 references
1988
0 references
A language is acceptable in the strong sense by a two-way nondeterministic Turing machine when all computation paths on every input stop and satisfy the space bound. The following main theorem is established. There exists a language which is acceptable in the strong sense by a two-way nondeterministic Turing machine in log log n space such that: if the language is not decidable by any two-way deterministic Turing machine in log log n space, then \(L\neq NL\).
0 references
space complexity
0 references
determinism
0 references
nondeterministic Turing machine
0 references
