A New Pebble Game that Characterizes Parallel Complexity Classes
From MaRDI portal
Publication:3835026
DOI10.1137/0218036zbMath0678.68047MaRDI QIDQ3835026
Martin Tompa, H. Venkateswaran
Publication date: 1989
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0218036
68Q25: Analysis of algorithms and problem complexity
91A05: 2-person games
94C99: Circuits, networks
Related Items
Pebbling dynamic graphs in minimal space, The complexity of short two-person games, Properties that characterize LOGCFL, Non-commutative arithmetic circuits: depth reduction and size lower bounds, Speedup of determinism by alternation for multidimensional Turing machines, Functions computable in polynomial space