A new kind of tradeoffs in propositional proof complexity

DOI10.1145/2858790zbMATH Open1394.03074OpenAlexW2322748670MaRDI QIDQ3177773FDOQ3177773

Authors: Alexander Razborov 

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2858790

Recommendations

• Width versus size in resolution proofs
• A tradeoff between length and width in resolution
• Theory and Applications of Models of Computation
• Supercritical space-width trade-offs for resolution
• On the virtue of succinct proofs

zbMATH Keywords

resolutiontradeoffhardness compression

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Cited In (8)

• Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
• Title not available (Why is that?)
• The treewidth of proofs
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• On derandomized composition of Boolean functions
• Supercritical Space-Width Trade-offs for Resolution
• On the virtue of succinct proofs
• On space and depth in resolution

This page was built for publication: A new kind of tradeoffs in propositional proof complexity

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