A new kind of tradeoffs in propositional proof complexity

DOI10.1145/2858790MaRDI QIDQ3177773zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

hardness compressionresolutiontradeoff

Mathematics Subject Classification ID

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

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

Cited in

(14)

• On space and depth in resolution
• The treewidth of proofs
• On derandomized composition of Boolean functions
• Monotone circuit lower bounds from resolution
• Supercritical space-width trade-offs for resolution
• On the virtue of succinct proofs
• Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Exponential separation between powers of regular and general resolution over parities
• A simple supercritical tradeoff between size and height in resolution
• Compressing CFI graphs and lower bounds for the Weisfeiler-Leman refinements
• Near-optimal lower bounds on quantifier depth and Weisfeiler-Leman refinement steps
• On the power and limitations of branch and cut
• Supercritical size-width tree-like resolution trade-offs for graph isomorphism

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)