- Machine Learning for SAT-solving heuristics
- Project Year:
2021
- REU Student (s):
Emily Chin | Harvey Mudd College CA
- Student 1 Institution:
Harvey Mudd College
- Project Mentor:
Periklis Papakonstantinou
- Project Mentor Area:
Management Science and Information Systems
- Project Abstract:
3-SAT is a known NP-Hard problem in theoretical computer science. In other words, it takes exponential time to deterministically solve this problem. However, there is a fairly effective random algorithm that finds the solution quickly most of the time, if there is one. This "Random Walk Algorithm" finds the solution by acting randomly at each timestep, but the results may not be completely random. This leads us to explore what features about an instance of the problem are important and how we can use these features to predict if a solution can be found at the end of a certain number of iterations of the algorithm. We used various machine learning techniques to make predictions using features that we found to be significant.
