Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution

摘要

A number of works have looked at the relationship between length and space of resolution proofs. A notorious question has been whether the existence of a short proof implies the existence of a proof that can be verified using limited space.In this paper we resolve the question by answering it negatively in the strongest possible way. We show that there are families of 6-CNF formulas of size n, for arbitrarily large n, that have resolution proofs of length O(n) but for which any proof requires space Omega(n / log n).  This is the strongest asymptotic separation possible since any proof of length O(n) can always be transformed into a proof in space O(n / log n).Our result follows by reducing the space complexity of so called pebbling formulas over a directed acyclic graph to the black-white pebbling price of the graph.The proof is somewhat simpler than previous results (in particular, those reported in [Nordstrom 2006, Nordstrom and Hastad 2008]) as it uses a slightly different flavor of pebbling formulas which allows for a rather straightforward reduction of proof space to standard black-white pebbling price.