Learning a SAT Solver from Single-Bit Supervision

By Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, David L. Dill. 2018

517 citations recorded by the source corpus.

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.

Subfields: Computer Networks and Communications, Information Systems, Management Science and Operations Research, Reinforcement Learning, Program Analysis & Verification

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

  1. Andrea Lodi
  2. Raquel Urtasun
  3. Yoshua Bengio
  4. Kevin P. Murphy
  5. Pushmeet Kohli
  6. Peter Clark
  7. William L. Hamilton
  8. Jure Leskovec

In Information Systems

  1. Hannaneh Hajishirzi
  2. Jonathan Berant
  3. Jure Leskovec
  4. Mohit Bansal
  5. Percy Liang
  6. Peter Clark
  7. Matt Gardner
  8. William L. Hamilton

In Management Science and Operations Research

  1. Yoshua Bengio
  2. Sergey Levine
  3. Roger Baker Grosse
  4. Richard S. Zemel
  5. Mohit Bansal
  6. Timothy P. Lillicrap
  7. Quoc V. Le
  8. Vladlen Koltun

In Reinforcement Learning

  1. Sergey Levine
  2. Pieter Abbeel
  3. Chelsea Finn
  4. Yuxi Li
  5. Nicolas Manfred Otto Heess
  6. Timothy P. Lillicrap
  7. Shimon Whiteson
  8. Razvan Pascanu

In Program Analysis & Verification

  1. Markus Norman Rabe
  2. Yuhuai Wu
  3. Christian Szegedy
  4. William L. Hamilton
  5. Stanislas Polu
  6. Wenda Li
  7. Oyvind Tafjord
  8. Peter Clark

Citations in the corpus