Matthew L Ginsberg (2015) "Satsisfiability and Systematicity", Volume 53, pages 497-540

PDF | doi:10.1613/jair.4684
Appendix 1 - FLEX code | Appendix 2 - STLSAT code

We introduce a new notion of systematicity for satisfiability algorithms with restarts, saying that an algorithm is strongly systematic if it is systematic independent of restart policy but weakly systematic if it is systematic for some restart policies but not others. We show that existing satisfiability engines are generally only weakly systematic, and describe FLEX, a strongly systematic algorithm that uses an amount of memory polynomial in the size of the problem. On large number factoring problems, FLEX appears to outperform weakly systematic approaches.

Click here to return to Volume 53 contents list