Alasdair Urquhart - Width and size of regular resolution proofs

lmcs:862 - Logical Methods in Computer Science, June 1, 2012, Volume 8, Issue 2 - https://doi.org/10.2168/LMCS-8(2:8)2012
Width and size of regular resolution proofsArticle

Authors: Alasdair Urquhart

    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.

    https://doi.org/10.2168/LMCS-8(2:8)2012
    Source: arXiv.org:1205.1050
    Volume: Volume 8, Issue 2
    Published on: June 1, 2012
    Imported on: January 16, 2012
    Keywords: Computer Science - Computational Complexity,Mathematics - Logic,F2.2,F4.1
    Licence: arXiv.org - Non-exclusive license to distribute
    Funding:
      Source : OpenAIRE Graph
    • Funder: Natural Sciences and Engineering Research Council of Canada

    3 Documents citing this article

    Share and export

    Consultation statistics

    This page has been seen 1415 times.
    This article's PDF has been downloaded 301 times.