The limits of tractability in resolution-based propositional proof systems

Article

Dantchev, S. and Martin, B. 2011. The limits of tractability in resolution-based propositional proof systems. Annals of Pure and Applied Logic. 163 (6), pp. 656-668. https://doi.org/10.1016/j.apal.2011.11.001
TypeArticle
TitleThe limits of tractability in resolution-based propositional proof systems
AuthorsDantchev, S. and Martin, B.
Abstract

We study classes of propositional contradictions based on the Least Number Principle (LNP) in the refutation system of Resolution and its generalisations with bounded conjunction, Res(k).

Keywordspropositional proof complexity; resolution with bounded conjunction; lower bounds
Research GroupFoundations of Computing group
PublisherElsevier
JournalAnnals of Pure and Applied Logic
ISSN0168-0072
Publication dates
Online03 Dec 2011
Publication process dates
Deposited20 Dec 2012
Output statusPublished
Additional information

Computability in Europe 2010

Digital Object Identifier (DOI)https://doi.org/10.1016/j.apal.2011.11.001
LanguageEnglish
Permalink -

https://repository.mdx.ac.uk/item/83wz0

Log in to edit
  • 17
    total views
  • 0
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as