From Small Space to Small Width in Resolution

DOI10.1145/2746339zbMath1367.03105OpenAlexW2150406686WikidataQ61732579 ScholiaQ61732579MaRDI QIDQ5277893

Jakob Nordström, Marc Vinyals, Yuval Filmus, Massimo Lauria, Mladen Mikša

Publication date: 12 July 2017

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2014/4466/

zbMATH Keywords

resolutionpolynomial calculusproof complexityPCRsmall spacepolynomial calculus resolutionsmall width

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Related Items (3)

On space and depth in resolution ⋮ Space characterizations of complexity measures and size-space trade-offs in propositional proof systems ⋮ The treewidth of proofs

Cites Work

• Unnamed Item
• A simplified way of proving trade-off results for resolution
• The intractability of resolution
• A combinatorial characterization of resolution width
• On the weak pigeonhole principle
• Pseudo-partitions, transversality and locality
• Space Complexity in Propositional Calculus
• Many hard examples for resolution
• Size-Space Tradeoffs for Resolution
• Hard examples for resolution
• Short proofs are narrow—resolution made simple
• Space complexity of random formulae in resolution
• Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds
• Time-space tradeoffs in resolution
• Some trade-off results for polynomial calculus

This page was built for publication: From Small Space to Small Width in Resolution