Strong ETH holds for regular resolution

DOI10.1145/2488608.2488669zbMath1293.03032OpenAlexW2041171215MaRDI QIDQ5495819

Christopher Beck, Russell Impagliazzo

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

lower boundsresolutionproof complexityquantum classical separation

Mathematics Subject Classification ID

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

Related Items (6)

Characterizing Tseitin-Formulas with Short Regular Resolution Refutations ⋮ Strong ETH and resolution via games and the multiplicity of strategies ⋮ Improving resolution width lower bounds for \(k\)-CNFs with applications to the strong exponential time hypothesis ⋮ An Introduction to Lower Bounds on Resolution Proof Systems ⋮ Unnamed Item ⋮ Characterizing Tseitin-formulas with short regular resolution refutations

This page was built for publication: Strong ETH holds for regular resolution