4
$\begingroup$

[Disclaimer: this is a rather specialized question]

It is known that techniques like Conflict-Driven Clause Learning (CDCL) and back-jumping -- which improved the Satisfiability (SAT) strategies exponentially -- were actually inspired [2] by Constraint Satisfaction Problem (CSP) techniques (so-called nogoods [1], or generalized nogoods).

But while SAT evolved and improved with these techniques, CSP doesn't seem to widely benefit from these ideas.

My question : why aren't these ideas ubiquitous in CSP like they are in SAT ? What happened ? What makes them unsuitable ? Is it "just" a question of domain size ?

Secondary question: are there any other ideas that jumped the divide between the two ? Instances of the CSP community inspiring the SAT community and/or vice versa ?

[1]: Generalized NoGoods in CSPs, G. Katsirelos, F. Bacchus

[2]: Using CSP Look-Back Techniques to Solve Real-World SAT Instances, R. Bayardo, R. Schrag

$\endgroup$

migrated from stackoverflow.com Mar 1 '17 at 20:49

This question came from our site for professional and enthusiast programmers.

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.