A New Pebble Game that Characterizes Parallel Complexity Classes

DOI10.1137/0218036zbMath0678.68047OpenAlexW2058868103MaRDI 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

zbMATH Keywords

parallel complexityLOGCFL\(AC^ k\)pebbling alternation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Circuits, networks (94C99)

Related Items

Speedup of determinism by alternation for multidimensional Turing machines, Positive and negative proofs for circuits and branching programs, The complexity of short two-person games, Properties that characterize LOGCFL, Pebbling dynamic graphs in minimal space, Succinct certification of monotone circuits, Characterizing Valiant's algebraic complexity classes, Functions computable in polynomial space, Two dynamic programming algorithms for which interpreted pebbling helps, Non-commutative arithmetic circuits: depth reduction and size lower bounds, Rounds versus time for the two person pebble game, Monomials in arithmetic circuits: complete problems in the counting hierarchy, Speedups of deterministic machines by synchronous parallel machines