NeuroSAT: Learning a SAT Solver from Single-Bit Supervision
Ғылым және технология
I will 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.
See more at www.microsoft.com/en-us/resea...
Пікірлер: 12
I just spent a long weekend trying to understand this and it was time well spent. So maybe the next weekend I'll get it.
Wow, shaping the message network like the problem/instance shape seems like a very powerful idea for other problems with structured input! Well done!
This Daniel guy is brilliant
@helix-phase
3 жыл бұрын
so intense
The iterative "state vector" makes sense, similar to a transformer. Seems like it's maintaining context as it iterates.
Well done! So does anyone get the trained model? I just find code without model at the site.
I can clearly see the "Bit Pattern".
The fact that everyone is so confused 😅🤣
wow
when i grow up i wan to be like shelldon
neuro.ai
camera guy, show the slide not the guy! can't follow