CRA-W Distributed Mentor Project

My Project

My project for this summer involves P and NP. This is actually a theoretical area of computer science in the area of algorithms. So what does any of it have to do with graphics? Well, first I pick a known NP problem, say satisfiability (SAT). Then I generate a whole lot of instances of SAT problems. Then I run all of these instances through a SAT solver to see how long it takes to solve them and how complex they are. And finally (here's the part you've been waiting for) I graph all of these data points to make a pretty and informative picture.

The goal of my project is to see if we can estimate, just by looking at the characteristics of a particular instance, how long that instance will take to solve. In other words, we are trying to predict whether a certain instance is really "hard" to solve, or if it is actually solvable in a reasonably short amount of time.