Complexity lower bounds for machine computing models

DOI10.1007/BF02104744zbMath0563.68046MaRDI QIDQ1057651

Anatoly Petrivich Beltiukov

Publication date: 1985

Published in: Journal of Soviet Mathematics (Search for Journal in Brave)

zbMATH Keywords

tailstime-space trade-offon-line computationssorting on RAM

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Research exposition (monographs, survey articles) pertaining to computer science (68-02)

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item