A New Kind of Tradeoffs in Propositional Proof Complexity

DOI10.1145/2858790zbMath1394.03074OpenAlexW2322748670MaRDI QIDQ3177773

Alexander A. 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

resolutiontradeoffhardness compression

Mathematics Subject Classification ID

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

Related Items (6)

On space and depth in resolution ⋮ Space characterizations of complexity measures and size-space trade-offs in propositional proof systems ⋮ The treewidth of proofs ⋮ On derandomized composition of Boolean functions ⋮ Supercritical Space-Width Trade-offs for Resolution ⋮ Unnamed Item

This page was built for publication: A New Kind of Tradeoffs in Propositional Proof Complexity