Complexity lower bounds for machine computing models
From MaRDI portal
Publication:1057651
DOI10.1007/BF02104744zbMath0563.68046MaRDI QIDQ1057651
Publication date: 1985
Published in: Journal of Soviet Mathematics (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68P10: Searching and sorting
68-02: Research exposition (monographs, survey articles) pertaining to computer science
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Hierarchies of Turing machines with restricted tape alphabet size
- Relating refined space complexity classes
- A hierarchy for nondeterministic time complexity
- Real time computation
- Tape bounds for time-bounded Turing machines
- On Time Versus Space
- Relations Among Complexity Measures
- Two-Tape Simulation of Multitape Turing Machines
- On-Line Turing Machine Computations
- On the Minimum Computation Time of Functions
- One-tape, off-line Turing machine computations