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 the normal view instead:
scientific article; zbMATH DE number 4064486
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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
0.801225483417511
0 references
0.7902999520301819
0 references
0.780091404914856
0 references
