Normalizing and accelerating RAM computations and the problem of reasonable space measures

DOI10.1007/BFB0032027MaRDI QIDQ4038687zbMATH OpenFDO

Authors Jiří Wiedermann

Publication date 18 May 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

invariance thesislogarithmic time complexityRAMtime complexity measuresuniform time complexities

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• The problem of space invariance for sequential machines
• scientific article; zbMATH DE number 512978
• A survey of space complexity
• scientific article; zbMATH DE number 3850476
• Invariance properties of RAMs and linear time

Cited in

(12)

• The problem of space invariance for sequential machines
• A survey of space complexity
• Invariance properties of RAMs and linear time
• Sorting, linear time and the satisfiability problem
• Delegating RAM Computations
• On the operating unit size of load/store architectures
• On time versus space III
• Fast Simulation of Turing Machines by Random Access Machines
• scientific article; zbMATH DE number 512978 (Why is no real title available?)
• On the notion of bit complexity
• Strict sequential P-completeness
• Parallel machine models: how they are and where are they going

This page was built for publication: Normalizing and accelerating RAM computations and the problem of reasonable space measures

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