Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
How hard is Wings of Vi?: An analysis of the computational complexity of the game Wings of Vi
KTH, School of Computer Science and Communication (CSC).
2015 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

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.

Place, publisher, year, edition, pages
2015. , 15 p.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-166728OAI: oai:DiVA.org:kth-166728DiVA: diva2:812014
Supervisors
Examiners
Available from: 2015-05-17 Created: 2015-05-14 Last updated: 2015-05-17Bibliographically approved

Open Access in DiVA

fulltext(893 kB)141 downloads
File information
File name FULLTEXT01.pdfFile size 893 kBChecksum SHA-512
7cabc769eb0d19625c09bfee7c74209b79cb2c21d6cb7d8410cc2101e6739453539a705f558a69ec19b7ab209710a362d3df5dc7491893b31bfe42f3c1a4b1c0
Type fulltextMimetype application/pdf

By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 141 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 88 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf