Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-16T13:07:00.638Z Has data issue: false hasContentIssue false

The complexity of resolution refinements

Published online by Cambridge University Press:  12 March 2014

Joshua Buresh-Oppenheim
Affiliation:
School of Computing Science, Simon Fraser University, Burnaby, BC, Canada. E-mail: jburesho@cs.sfu.ca
Toniann Pitassi
Affiliation:
Computer Science Department, University of Toronto, Toronto, ON, Canada. E-mail: toni@cs.toronto.edu

Abstract

Resolution is the most widely studied approach to propositional theorem proving. In developing efficient resolution-based algorithms, dozens of variants and refinements of resolution have been studied from both the empirical and analytic sides. The most prominent of these refinements are: DP (ordered), DLL (tree), semantic, negative, linear and regular resolution. In this paper, we characterize and study these six refinements of resolution. We give a nearly complete characterization of the relative complexities of all six refinements. While many of the important separations and simulations were already known, many new ones are presented in this paper; in particular, we give the first separation of semantic resolution from general resolution. As a special case, we obtain the first exponential separation of negative resolution from general resolution. We also attempt to present a unifying framework for studying all of these refinements.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable