DocumentCode
303348
Title
A NN algorithm for Boolean satisfiability problems
Author
Spears, William M.
Author_Institution
Naval Res. Lab., Washington, DC, USA
Volume
2
fYear
1996
fDate
3-6 Jun 1996
Firstpage
1121
Abstract
Satisfiability (SAT) refers to the task of finding a truth assignment that makes an arbitrary Boolean expression true. This paper compares a neural network algorithm (NNSAT) with GSAT, a greedy algorithm for solving satisfiability problems. GSAT can solve problem instances that are difficult for traditional satisfiability algorithms. Results suggest that NNSAT scales better as the number of variables increase, solving at least as many hard SAT problems
Keywords
Boolean functions; Hopfield neural nets; computability; graph theory; Boolean satisfiability problems; GSAT; NNSAT; arbitrary Boolean expression; greedy algorithm; neural network algorithm; truth assignment; Artificial intelligence; Computational complexity; Greedy algorithms; Laboratories; Logic; Neural networks; Operations research; Performance evaluation; Testing; Tree graphs;
fLanguage
English
Publisher
ieee
Conference_Titel
Neural Networks, 1996., IEEE International Conference on
Conference_Location
Washington, DC
Print_ISBN
0-7803-3210-5
Type
conf
DOI
10.1109/ICNN.1996.549055
Filename
549055
Link To Document