211service.com
Super Mario Bros visade sig vara NP-hård
Tillbaka i januari tittade vi på Giovanni Vigliettas arbete vid University if Pisa i Italien som hade bevisat beräkningskomplexiteten hos många datorspel från 80- och 90-talen, som Pac-Man och Tron.
Viglietta påpekade att denna typ av analys är onödig för moderna spel eftersom de flesta innehåller Turing-ekvivalenta skriptspråk som enkelt tillåter design av oavgjorda pussel som en del av spelet.
Men det lämnar fortfarande många klassiker som ännu inte är klassificerade.
Idag fyller Greg Aloupis vid Free University of Brussels i Belgien och ett par kompisar det hålet, åtminstone delvis.
Dessa killar bevisar att flera klassiska Nintendo-spel från 80-talet alla är NP-hårda. Listan inkluderar de tre första inkarnationerna av Super Mario Bros, Donkey Kong och alla Legend of Zelda-spel.
Alla dessa spel är i huvudsak desamma genom att de börjar vid en specifik punkt med syftet att nå något mål. Frågan Aloupis och co ställer är denna: med tanke på utgångsläget, är det möjligt att nå målet?
Om det är svårt att avgöra ens denna fråga, så är det verkligen svårt att hitta en optimal väg, säger de.
I detta sammanhang fortsätter de med att visa att alla spel i huvudsak är versioner av ett annat problem som kallas 3-SAT, som är känt för att vara NP-komplett. Processen här är att visa att 3SAT reducerar till dessa problem under vissa omständigheter, vilket bevisar att de är NP-hårda.
Så om din ungdom missbrukades med att spela Super Mario Bros, Donkey Kong eller något av de andra spelen som dessa killar visar sig vara NP-Hard, då kan det ge lite tröst att du inte slösar bort din tid helt att veta hur svåra de faktiskt var. Återigen, förmodligen inte!
Ref: arxiv.org/abs/1203.1895 : Klassiska Nintendo-spel är (NP-)Hårda