Paper Information
| Title | Online Games as Social-Computational Systems for Solving NP-complete Problems |
| Presenter(s) | Charles Cusack, Jeff Largent, Ryan Alfuth and Kimberly Klask |
| Session | Problem solving games |
| Time | Saturday, October 23, 11:30a-12:30p |
| Location | Green Room |
| Format | Paper Presentation |
| Description | This paper discusses the applicability of human computing games to solving instances of NP-complete problems, a collection of problems that cannot currently be efficiently solved with computers. The idea is to leverage the diversity offered by a large group of humans--that is, utilize the different skills humans have that computers don't as well as the different perspectives of the individuals who plays the games. To explore this possibility, we created Pebble It, a suite of games that can be used to solve instances of problems related to a mathematical concept called graph pebbling. Several examples are presented that demonstrate the benefits of this approach to problem solving. We conclude by discussing how these games can link players and researchers to form a social-computational system that can strengthen research--sometimes in unexpected ways. |
| More | View PDF of full paper |