Speedups of deterministic machines by synchronous parallel machines
From MaRDI portal
Publication:1074339
DOI10.1016/0022-0000(85)90011-XzbMath0589.68040OpenAlexW2084764151MaRDI QIDQ1074339
Martin Tompa, Patrick W. Dymond
Publication date: 1985
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(85)90011-x
Related Items
A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators, Speedup of determinism by alternation for multidimensional Turing machines, Cumulative Space in Black-White Pebbling and Resolution, On nondeterminism in parallel computation, Rounds versus time for the two person pebble game, A generalization of Spira's theorem and circuits with small segregators or separators, Reversible Pebble Game on Trees, On time versus space III, Pebbling meets coloring: reversible pebble game on trees, The size and depth of layered Boolean circuits, Parallelizing time with polynomial circuits, The complexity of short two-person games, On uniformity and circuit lower bounds, Two dynamic programming algorithms for which interpreted pebbling helps, Alternating time versus deterministic time: A separation, Rounds versus time for the two person pebble game
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On nondeterminism in parallel computation
- On alternation
- On alternation. II. A graph theoretic approach to determinism versus nondeterminism
- On uniform circuit complexity
- Towards a complexity theory of synchronous parallel computation
- A characterization of the power of vector machines
- Circuit size is nonlinear in depth
- Tape bounds for time-bounded Turing machines
- A New Pebble Game that Characterizes Parallel Complexity Classes
- Alternation
- On Time Versus Space
- On Relating Time and Space to Size and Depth
- Space bounds for a game on graphs
- Correction to “Space Bounds for a Game on Graphs” by Wolfgang J. Paul, Robert Endre Tarjan and James R. Celoni
- A unified approach to models of synchronous parallel machines
- Parallelism in random access machines
