Dissertation/Thesis Abstract

Pebble Games and Complexity
by Chan, Siu Man, Ph.D., University of California, Berkeley, 2013, 74; 3593787
Abstract (Summary)

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.

Indexing (document details)
Advisor: Mossel, Elchanan, Trevisan, Luca
Commitee: Aldous, David, Vazirani, Umesh
School: University of California, Berkeley
Department: Computer Science
School Location: United States -- California
Source: DAI-B 75/01(E), Dissertation Abstracts International
Source Type: DISSERTATION
Subjects: Computer science
Keywords: Depth complexity, Parallel complexity, Pebble games
Publication Number: 3593787
ISBN: 9781303371783
Copyright © 2019 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy
ProQuest