Pebble Games and Complexity
Pebble Games and Complexity
复制标题
Pebble 游戏和复杂性
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Siu Man Chan
中科院分区：
文献类型：
--
作者：
Elchanan Mossel;L. Trevisan;Siu Man Chan
我们研究卵石游戏与复杂性之间的联系。
We study the connection between pebble games and complexity.
First, we derive complexity results using pebble games. It is shown that three pebble games used for studying computational complexity are equivalent: namely, the two-person pebble game of Dymond-Tompa, the two-person pebble game of Raz-McKenzie, and the one-person reversible pebble game of Bennett have the same pebble costs over any directed acyclic graph. The three pebble games have been used for studying parallel complexity and for proving lower bounds under restricted settings, and we show one more such lower bound on circuit-depth.
Second, the pebble costs are applied to proof complexity. Concerning a family of unsatisfiable CNFs called pebbling contradictions, the pebble cost in any of the pebble games controls the scaling of some parameters of resolution refutations. Namely, the pebble cost controls the minimum depth of resolution refutations and the minimum size of tree-like resolution refutations.
Finally, we study the space complexity of computing the pebble costs and of computing the minimum depth of resolution refutations. It is PSPACE-complete to compute the pebble cost in any of the three pebble games, and to compute the minimum depth of resolution refutations.