Urquhart, Alasdair - Width and size of regular resolution proofs

lmcs:862 - Logical Methods in Computer Science, June 1, 2012, Volume 8, Issue 2
Width and size of regular resolution proofs

Authors: Urquhart, Alasdair

This paper discusses the topic of the minimum width of a regular resolution refutation of a set of clauses. The main result shows that there are examples having small regular resolution refutations, for which any regular refutation must contain a large clause. This forms a contrast with corresponding results for general resolution refutations.

DOI : 10.2168/LMCS-8(2:8)2012
Volume: Volume 8, Issue 2
Published on: June 1, 2012
Submitted on: January 16, 2012
Keywords: Computer Science - Computational Complexity,Mathematics - Logic,F2.2,F4.1


Consultation statistics

This page has been seen 165 times.
This article's PDF has been downloaded 78 times.