The limits of tractability in resolution-based propositional proof systems
type: Item
instance of: scholarly article
title: The limits of tractability in resolution-based propositional proof systems
zbMATH Open document ID: 1251.03070
author: Barnaby Martin
author: Stephan Stoyanov Danchev
published in: Annals of Pure and Applied Logic
publication date: 2012-03-29T00:00:00Z
Mathematics Subject Classification ID: 03F20
zbMATH DE Number: 6019354
zbMATH Keywords: propositional proof complexity
zbMATH Keywords: resolution with bounded conjunction
zbMATH Keywords: lower bounds
MaRDI profile type: Publication
full work available at URL: j.apal.2011.11.001
OpenAlex ID: W1521370165
cites work: Separation results for the size of constant-depth propositional proofs
cites work: Q3002766
cites work: Q3549627
cites work: The Limits of Tractability in Resolution-Based Propositional Proof Systems
cites work: Computer Science Logic
cites work: On the weak pigeonhole principle
cites work: Q4856172
cites work: Lower bounds to the size of constant-depth propositional proofs
cites work: Short proofs for tricky formulas
cites work: Probability and Computing
cites work: Proofs as Games
cites work: A complexity gap for tree resolution
cites work: A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
cites work: The provably total search problems of bounded arithmetic
DOI: 10.1016/J.APAL.2011.11.001
description: scientific article; zbMATH DE number 6019354