Pokemon og Super Mario er NP-harde
Hvis du synes spill som Super Mario Brothers, Donkey Kong og Pokemon er vanskelige kan du nå ta det med ro. Det har nylig blitt bevist at selv ikke verdens fremste informatikere klarer å finne gode algoritmer for disse spillene.
Hovedinnhold
Tre algoritmeforskere, bl.a. Erik Demaine fra MIT, har nylig vist at mange klassiske Nintendo-spill er NP-harde. Se deres artikkel fritt tilgjengelig på arxiv her http://arxiv.org/abs/1203.1895 . NP-hardhetsbevis er pensum i vårt kurs INF234 ved institutt for informatikk og artikkelen burde være av interesse for alle spill-freaks. Et slikt bevis krever at man bygger 'gadgets' som viser at det er like vanskelig å velge riktig løsning i f.eks. Super Mario Brothers som det er å tilfredsstille et generellt logisk utsagn. Hvert spill er generalisert til å avgjøre om man kan gå fra en gitt start posisjon til en gitt slutt posisjon. Alle spillene er bevist NP-harde, noen er vist å være NP-komplette, og noen er PSPACE-komplette (pensum INF235).
