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 (62)
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 ⋮ On the target pebbling conjecture ⋮ 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
This page was built for publication: On Time Versus Space
