pith. sign in

arxiv: 1310.7627 · v2 · pith:HTSARFYKnew · submitted 2013-10-28 · 💻 cs.CC · cs.LO

Hardness measures and resolution lower bounds

classification 💻 cs.CC cs.LO
keywords measureshardnessresolutionbeenboundsclause-setscomplexitydifferent
0
0 comments X
read the original abstract

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).

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.