Cumulative Space in Black-White Pebbling and Resolution
Cumulative Space in Black-White Pebbling and Resolution
复制标题
黑白卵石的累积空间和分辨率
DOI：
10.4230/lipics.itcs.2017.38
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Marc Vinyals
中科院分区：
文献类型：
--
作者：
J. Alwen;Susanna F. de Rezende;Jakob Nordström;Marc Vinyals
我们研究了空间复杂性和时间间隔的权衡，而不是关注峰值记忆使用，而是整个计算过程中的整体内存消耗。 [Alwen and Serbinenko 2015]为平行黑色卵石的计算模型引入了这种累积空间度量，作为获得加密结果的工具。相反，我们认为非确定性的黑白卵石游戏，并证明了最佳的累积空间较低的界限和权衡，为了最大程度地减少卵石时间，在很大一部分卵石中，空间必须保持较大。
我们还启动了证明复杂性累积空间的研究，该领域在过去的10 - 15年中对其他空间复杂性测量进行了广泛研究。在[Ben-Sasson和Nordstrom 2008，2011]中，使用并扩展了证明复杂性与卵石游戏之间的连接，我们为（甚至是平行版本的）证明系统获得了一些强大的累积空间结果，并概述了研究的一些可能的未来方向我们认为，这是自然而有趣的空间度量。
We study space complexity and time-space trade-offs with a focus not on peak memory usage but on overall memory consumption throughout the computation. Such a cumulative space measure was introduced for the computational model of parallel black pebbling by [Alwen and Serbinenko 2015] as a tool for obtaining results in cryptography. We consider instead the nondeterministic black-white pebble game and prove optimal cumulative space lower bounds and trade-offs, where in order to minimize pebbling time the space has to remain large during a significant fraction of the pebbling.
We also initiate the study of cumulative space in proof complexity, an area where other space complexity measures have been extensively studied during the last 10-15 years. Using and extending the connection between proof complexity and pebble games in [Ben-Sasson and Nordstrom 2008, 2011], we obtain several strong cumulative space results for (even parallel versions of) the resolution proof system, and outline some possible future directions of study of this, in our opinion, natural and interesting space measure.