A New Pebble Game that Characterizes Parallel Complexity Classes

A new two-person pebble game that models parallel computations is defined. This game extends the two-person pebble game defined in [DT85] and is used to characterize two natural parallel complexity classes, namely LOGCFL and AG1. The characterizations show a fundamental way in which the computations in these two classes differ. This game model also unifies the proofs of some well known results of complexity theory.

Authors

• H. Venkateswaran
• Martin Tompa

Keywords

• Computational modeling
• Turing machines
• Concurrent computing
• Switches
• Game theory
• Circuits
• Computer science
• Complexity theory
• Polynomials
• Phase change random access memory
• Pebble Game
• Parallelization
• Complex Class
• Fundamental Ways
• Game Model
• Computational Model
• Language Teaching
• Constant Factor
• Rules Of The Game
• Subtree
• Binary Tree
• First-order Logic
• Measures Of Resources
• Interest In Resources
• Turing Machine
• Round Of The Game
• Language Recognition
• Current Round
• OR Gate
• Original Game
• Tens Of Times
• Universal Quantifier
• Proof Let
• Proof Of Theorem
• Order Logic
• Time And Space
• Directed Graph
• Out-degree