# Complexity Measure and Practical Hardness of SAT

I am study this paper "Relating Proof Complexity Measures and Practical Hardness of SAT". Here the authors propose to use pebble formulas to find a relation between these and practical SAT performances using as measure the space of resolution. My question is is it to possible to extend that relation beyond of pebble formulas? For example for a random CNF formula.

• For random $k$-SAT, google for "phase transition". You will find the clause-to-variables ratio, which is a widely used heuristic. – Juho Jan 18 '16 at 10:15
• Otherwise, see this question. – Juho Jan 18 '16 at 11:26