2013/10/28 by Olaf Beyersdorff, Beyersdorff, Olaf, Oliver Kullmann +1
Chemistry · Computer Science · #Computational Complexity (cs.CC) #F.2.2 #FOS: Computer and information sciences #Formal Methods in Verification #Logic in Computer Science (cs.LO) #Logic, programming, and type systems #Synthetic Organic Chemistry Methods
paper · pdf · doi:10.48550/arxiv.1310.7627
openalex publication_date 2013/10/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Various "hardness" measures have been studied for resolution, providing theoretical insight into the proof complexity of resolution and its fragments, as well as explanations for the hardness of instances in SAT solving. In this report we aim at a unified view of a number of hardness measures, including different measures of width, space and size of resolution proofs. We also extend these measures to all clause-sets (possibly satisfiable).