Stochastic Local Search in k-Term DNF Learning

Ulrich Rückert and Stefan Kramer

A novel native stochastic local search algorithm for solving k-term DNF problems is presented. It is evaluated on hard k-term DNF problems that lie on the phase transition and compared to the performance of GSAT and WalkSAT type algorithms on SAT encodings of k-term DNF problems. We also evaluate state-of-the-art separate and conquer algorithms on these problems. Finally, we demonstrate the practical relevance of our algorithm on a chess endgame database.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.