Learning a SAT Solver from Single-Bit Supervision
  We present NeuroSAT, a message passing neural network that learns to solve
SAT problems after only being trained as a classifier to predict
satisfiability. Although it is not competitive with state-of-the-art SAT
solvers, NeuroSAT can solve problems that are substantially larger and more
difficult than it ever saw during training by simply running for more
iterations. Moreover, NeuroSAT generalizes to novel distributions; after
training only on random SAT problems, at test time it can solve SAT problems
encoding graph coloring, clique detection, dominating set, and vertex cover
problems, all on a range of distributions over small random graphs.
