1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.