On Time Versus Space
From MaRDI portal
Publication:4131020
DOI10.1145/322003.322015zbMath0358.68082OpenAlexW2062934582MaRDI QIDQ4131020
John E. Hopcrofts, Wolfgang J. Paul, Leslie G. Valiant
Publication date: 1977
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322003.322015
Related Items
Space-time tradeoffs for linear recursion, Static-memory-hard functions, and modeling the cost of space vs. time, Cumulative Space in Black-White Pebbling and Resolution, Proofs of Space, Rounds versus time for the two person pebble game, Expanders, randomness, or time versus space, Parallel computation with threshold functions, Min Cut is NP-complete for edge weighted trees, Relativized alternation and space-bounded computation, Amplifying circuit lower bounds against polynomial time, with applications, On time versus space III, On nontrivial separators for \(k\)-page graphs and simulations by nondeterministic one-tape Turing machines, On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape, On relationships between complexity classes of Turing machines, On time hierarchies, On alternation, Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks, On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\), A note on the pebble game, The space complexity of pebble games on trees, Sustained space and cumulative complexity trade-offs for data-dependent memory-hard functions, Unnamed Item, The parallel reversible pebbling game: analyzing the post-quantum security of iMHFs, Observations on the complexity of regular expression problems, A comparison of two variations of a pebble game on graphs, The size and depth of layered Boolean circuits, Parallelizing time with polynomial circuits, A space bound for one-tape multidimensional Turing machines, On time versus space. II, Classifying the computational complexity of problems, Pebble games for studying storage sharing, Number of quantifiers is better than number of tape cells, Time complexity of multidimensional Turing machines, Extreme time-space tradeoffs for graphs with small space requirements, On the cost of recomputing: tight bounds on pebbling with faults, Unnamed Item, On the relationship between deterministic time and deterministic reversal, On Reducing the Space Requirements of a Straight-Line Algorithm, Towards separating nondeterminism from determinism, On 3-pushdown graphs with large separators, Time-space tradeoffs for SAT on nonuniform machines, Complexity of Nondeterministic Multitape Computations Based on Crossing Sequences, Nullstellensatz size-degree trade-offs from reversible pebbling, Time-space trade-offs in a pebble game, Synchronizing Automata over Nested Words, Alternating time versus deterministic time: A separation, Sorting, linear time and the satisfiability problem, A partial k-arboretum of graphs with bounded treewidth, Searching and pebbling, Improved simulation of nondeterministic Turing machines, Nonuniform complexity classes specified by lower and upper bounds, On the cost of recomputing: Tight bounds on pebbling with faults, Bandwidth and pebbling, Space-bounded simulation of multitape turing machines, Nullstellensatz size-degree trade-offs from reversible pebbling, A view of computability on term algebras, Data structures for distributed counting, Complexity lower bounds for machine computing models, The complexity of matrix transposition on one-tape off-line Turing machines, Rounds versus time for the two person pebble game, Speedups of deterministic machines by synchronous parallel machines
