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 (13)

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

This page was built for publication: A New Pebble Game that Characterizes Parallel Complexity Classes