Width versus size in resolution proofs

DOI10.1016/J.TCS.2007.05.022MaRDI QIDQ2382288zbMATH OpenOpenAlexFDO

Authors Alasdair Urquhart

Publication date 28 September 2007

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2007.05.022

zbMATH Keywords

complexity of proofsresolution proofswidth-size tradeoffs

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Recommendations

• Theory and Applications of Models of Computation
• Short proofs are narrow -- resolution made simple
• Short proofs are narrow—resolution made simple
• Hard examples for resolution
• Optimality of size-width tradeoffs for resolution

Cites work

• An exponential separation between the parity principle and the pigeonhole principle
• Hard examples for resolution
• scientific article; zbMATH DE number 3904557 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 1223618 (Why is no real title available?)
• scientific article; zbMATH DE number 1559594 (Why is no real title available?)
• Many hard examples for resolution
• On the complexity of regular resolution and the Davis-Putnam procedure
• Optimality of size-width tradeoffs for resolution
• Regular resolution lower bounds for the weak pigeonhole principle
• Resolution lower bounds for perfect matching principles
• Resolution lower bounds for the weak functional pigeonhole principle.
• Resolution lower bounds for the weak pigeonhole principle
• Resolution proofs of generalized pigeonhole principles
• Short proofs are narrow—resolution made simple
• The intractability of resolution

Cited in

(12)

• Optimality of size-width tradeoffs for resolution
• Resolution proofs of matching principles
• A tradeoff between length and width in resolution
• Short proofs are narrow -- resolution made simple
• Width and size of regular resolution proofs
• A new kind of tradeoffs in propositional proof complexity
• Hard examples for resolution
• Short proofs are narrow—resolution made simple
• Resolution and the binary encoding of combinatorial principles
• scientific article; zbMATH DE number 7561756 (Why is no real title available?)
• Theory and Applications of Models of Computation
• Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs

This page was built for publication: Width versus size in resolution proofs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2382288)