Milking the Aanderaa argument
From MaRDI portal
Publication:918198
DOI10.1016/0890-5401(90)90005-3zbMath0705.68050MaRDI QIDQ918198
Ramamohan Paturi, Janos Simon, Joel I. Seiferas, Richard E. Newman-Wolfe
Publication date: 1990
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1802/5963
68Q25: Analysis of algorithms and problem complexity
03D15: Complexity of computation (including implicit computational complexity)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An information-theoretic approach to time bounds for on-line computation
- Real time computation
- On-line simulation of k + 1 tapes by k tapes requires nonlinear time
- Two nonlinear lower bounds for on-line computations
- Space Lower Bounds for Maze Threadability on Restricted Machines
- Two-Tape Simulation of Multitape Turing Machines
- THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS