Finding good heuristics for a nondeterministic polynomial-time (NP) problem is a very important research goal that is mostly addressed on a case-by-case basis. This paper takes a different path: a classic NP problem, 3-SAT, is used as a test bed to assess the performance of using machine learning (ML) methods to automatically derive solver heuristics. The idea behind using this approach is that it is very general and could be used with many different problems. Good features for describing each instance of the problem could be extracted and then used to train a machine learning model.

The results obtained showed a great reduction in the branching factor for the tested 3-SAT instances. However, as there is no free lunch, the total execution time using the authors’ approach was not smaller than the one obtained using naive backtracking, given the added overhead of the ML approach.

The paper reminds us that ML can be used as a “universal heuristic generator,” but, as the results for the tested problems indicate, we can probably do better with specialized techniques when they are available; for the moment, NP problems remain NP.