AbstractsComputer Science

Computational complexity theory is the study of the inherent difficulty of different computational problems. By determining the complexity class of a problem you can learn a lot about how hard the problem is to solve. For games, their complexity class determines sort of an upper limit to how hard they can be. All NP-complete games can be made to be both extremely difficult to play and to analyze. The purpose of this study is to analyze the computational complexity of the game Wings of Vi, where it is shown to be both NP-hard and in NP, and thus NP-complete.