Complexity lower bounds for machine computing models

DOI10.1007/BF02104744MaRDI QIDQ1057651zbMATH OpenFDO

Authors Anatoly Petrivich Beltiukov

Publication date 1985

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

Full work available at URL https://doi.org/10.1007/BF02104744

zbMATH Keywords

on-line computationssorting on RAMtailstime-space trade-off

Mathematics Subject Classification ID

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

Review text

Translation from Zap. Nauchn. Semin. Leningr. Otd. Mat. Inst. Steklova 118, 4-24 (Russian) (1982; Zbl 0494.68058).

Cites work

• A hierarchy for nondeterministic time complexity
• Hierarchies of Turing machines with restricted tape alphabet size
• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 3653573 (Why is no real title available?)
• scientific article; zbMATH DE number 3655356 (Why is no real title available?)
• scientific article; zbMATH DE number 3685459 (Why is no real title available?)
• scientific article; zbMATH DE number 3723863 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3596248 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• On the Minimum Computation Time of Functions
• On Time Versus Space
• On-Line Turing Machine Computations
• One-tape, off-line Turing machine computations
• Real time computation
• Relating refined space complexity classes
• Relations Among Complexity Measures
• Tape bounds for time-bounded Turing machines
• Two-Tape Simulation of Multitape Turing Machines

Cited in

(2)

• scientific article; zbMATH DE number 5354044 (Why is no real title available?)
• scientific article; zbMATH DE number 2026795 (Why is no real title available?)

This page was built for publication: Complexity lower bounds for machine computing models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1057651)