Abstract

We present NeuroSAT, a message passing neural network that learns to solveSAT problems after only being trained as a classifier to predictsatisfiability. Although it is not competitive with state-of-the-art SATsolvers, NeuroSAT can solve problems that are substantially larger and moredifficult than it ever saw during training by simply running for moreiterations. Moreover, NeuroSAT generalizes to novel distributions; aftertraining only on random SAT problems, at test time it can solve SAT problemsencoding graph coloring, clique detection, dominating set, and vertex coverproblems, all on a range of distributions over small random graphs.

 

Quick Read (beta)