Graph Neural Networks and Boolean Satisfiability

Preprint English OPEN
Bünz, Benedikt; Lamm, Matthew;
  • Subject: Computer Science - Artificial Intelligence

In this paper we explore whether or not deep neural architectures can learn to classify Boolean satisfiability (SAT). We devote considerable time to discussing the theoretical properties of SAT. Then, we define a graph representation for Boolean formulas in conjunctive ... View more
  • References (10)

    Stephen A. Cook. The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC '71, pages 151-158, New York, NY, USA, 1971. ACM.

    David Devlin and Barry O'Sullivan. B.: Satisfiability as a classification problem. In Proc. of the 19th Irish Conf. on Artificial Intelligence and Cognitive Science, 2008.

    Shai Haim and Toby Walsh. Restart strategy selection using machine learning techniques. In Oliver Kullmann, editor, Theory and Applications of Satisfiability Testing - SAT 2009, volume 5584 of Lecture Notes in Computer Science, pages 312-325. Springer Berlin Heidelberg, 2009.

    J.J. Hopfield and D.W. Tank. neural computation of decisions in optimization problems. Biological Cybernetics, 52(3):141-152, 1985.

    James L. Johnson. A neural network approach to the 3-satisfiability problem. Journal of Parallel and Distributed Computing, 6(2):435 - 449, 1989.

    Lorenza Saitta, Attilio Giordana, and Antoine Cornujols. Phase Transitions in Machine Learning. Cambridge University Press, New York, NY, USA, 1st edition, 2011.

    Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. Computational capabilities of graph neural networks. Neural Networks, IEEE Transactions on, 20(1):81-102, 2009.

    Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. Neural Networks, IEEE Transactions on, 20(1):61-80, 2009.

    Bart Selman, Henry Kautz, and Bram Cohen. Local search strategies for satisfiability testing. In DIMACS SERIES IN DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, pages 521-532, 1995.

    Richard Socher, Brody Huval, Christopher D. Manning, and Andrew Y. Ng. Semantic Compositionality Through Recursive Matrix-Vector Spaces. In Proceedings of the 2012 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2012.

  • Similar Research Results (3)
  • Metrics
Share - Bookmark