Mathematical Application of Push3

This week, we took a good hard look at the SAT problem.

There are two ways to solve SAT efficiently: stochastic local search, and variants on the DPLL algorithm. I looked at local search, and Connor looked at DPLL. Today we’re going to compare notes.

I read the Fukunaga paper: it seems that using GP to evolve heuristics for which bit to flip next was a highly effective strategy. This is encouraging. I also got a textbook about stochastic local search in general, which has been useful for background.

It seems to me that a very useful contribution to the literature here could be an evolved DPLL/local search hybrid. My concern is that we could fall into the same trap that Fukunaga did in his first CLASS system, where sophisticated primitives didn’t buy him much at all. I will need to read that paper as well.

This entry was posted on September 30, 2009 at 11:47 am and is filed under Uncategorized.