You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

On Linear Resolution

Article type: Research Article

Authors: Buss, Sama; * | Johannsen, Janb; **

Affiliations: [a] Department of Mathematics, University of California, San Diego, La Jolla, CA 92093-0112, USA. E-mail: [email protected] | [b] Institut für Informatik, Ludwig-Maximilians-Universität München, 80538 München, Germany. E-mail: [email protected]

Note: [*] Supported in part by NSF grant CCR-1213151. Work performed in part at the Special Semester on Complexity Theory at St. Petersburg State University, and Dagstuhl seminar 16381 “SAT and Interactions”.

Note: [**] Work performed in part during a visit at UCSD, the Special Semester on Complexity Theory at St. Petersburg State University, and Dagstuhl seminar 16381 “SAT and Interactions”.

Keywords: s-resolution, linear resolution, tree-like resolution, regular resolution, proof complexity

DOI: 10.3233/SAT190112

Journal: Journal on Satisfiability, Boolean Modeling and Computation, vol. 10, no. 1, pp. 23-35, 2016

Published: 1 January 2017
Get PDF open access

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 tautologies (also known as “graph tautologies”), and the guarded ordering tautologies. This shows that regular resolution does not simulate linear resolution.

Show more