Charles Cusack, Department of Computer Science

Research Area: Human Computing Games

Research Description:

Problems in the complexity class NP-complete are all equivalent in the sense that an efficient algorithm for any of them can essentially be applied to all of them. One of the most important open problems in theoretical computer science is if such an efficient algorithm can be found or it can be proven that one does not exist. Since many important practical problems related to routing, scheduling, resource allocation, etc., are NP-complete, the solution to this problem is of interest to just about everyone.

Researchers trying to solve this problem generally come from a very narrowly defined group: computer scientists, mathematicians, scientists, and engineers. The goal of my research is to use crowdsourcing techniques to allow a more diverse audience to contribute to the solution of this problem. My research group is currently creating online games based on instances of NP-complete problems that record player actions. We present instances of problems to see what techniques players employ to solve them, and will soon start giving them unsolved instances to see if they are able to solve them when the best-known algorithms cannot. Eventually we will study the gameplay of the best players and attempt to develop algorithms based on their strategies.

We are currently focusing on games related to graph pebbling problems. The next round of games will be related to other NP-complete problems on graphs, since the software has been designed to make implementing other graph games relatively easy. We will also create versions of one or more popular puzzle games based on NP-complete problems, like Tetris, Minesweeper, and FreeCell, that will allow player strategies to be examined.

Charles Cusack,
Assistant Professor, Computer Science

Hope College, Department of Computer Science

http://www.hope.edu/cs/cusack/index.html