Sam Buss and Jan Johannsen
    "On Linear Resolution
    Preprint, December 2016.
    Journal of Satisfiability, Boolean Modeling and Computation, to appear.

    Download preprint.

Abstract: We discuss the relationship between linear resolution, s-linear resolution and other fragments of resolution, including tree-like resolution, regular resolution and general resolution. We also discuss linear resolution with restarts. We present polynomial-size linear resolution proofs of the ordering tautology, and the guarded ordering tautologies. This shows that regular resolution does not simulate linear resolution.

Back to Sam Buss's publications page.