关键词：卵石游戏；复杂性；联系
摘 要：We study the connection between pebble games and complexity. First, we derive complexity results using pebble games. Second, the pebble costs are applied to proof complexity. Finally, we study the space complexity of computing the pebble costs and of computing the minimum depth of resolution refutations.