Size space tradeoffs for resolution

Eli Ben‐Sasson

2002 · 33 citations · 33 references

Concepts

Abstract

We investigate tradeoffs of various important complexity measures such as size, space and width. We show examples of CNF formulas that have optimal proofs with respect to any one of these parameters, but optimizing one parameter must cost an increase in the other. These results, the first of their kind, have implications on the efficiency (or rather, inefficiency) of some commonly used SAT solving heuristics.Our proof relies on a novel and somewhat surprising connection of the variable space of a proof, to the black white pebbling measure of an underlying graph.

References

33