Short proofs are narrow—resolution made simple
From MaRDI portal
Publication:2819584
DOI10.1145/301250.301392zbMath1346.68173OpenAlexW2130847546MaRDI QIDQ2819584
Publication date: 29 September 2016
Published in: Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/301250.301392
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Related Items
Mutilated chessboard problem is exponentially hard for resolution ⋮ A dichotomy for local small-bias generators ⋮ Resolution and binary decision diagrams cannot simulate each other polynomially ⋮ The complexity of proving that a graph is Ramsey ⋮ An Upper Bound for Resolution Size: Characterization of Tractable SAT Instances ⋮ Lifting lower bounds for tree-like proofs ⋮ The complexity of properly learning simple concept classes ⋮ Cutting Planes and the Parameter Cutwidth ⋮ Space complexity of random formulae in resolution ⋮ Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution ⋮ Resolution and the binary encoding of combinatorial principles ⋮ Relative efficiency of propositional proof systems: Resolution vs. cut-free LK ⋮ Unnamed Item ⋮ Space bounds for resolution
This page was built for publication: Short proofs are narrow—resolution made simple
