Super Mario Bros izrādījās NP-Hard

Janvārī mēs apskatījām Džovanni Viglietas darbu Pizas Universitātē Itālijā, kurš bija pierādījis daudzu 80. un 90. gadu datorspēļu, piemēram, Pac-Man un Tron, skaitļošanas sarežģītību.

Viglietta norādīja, ka šāda veida analīze mūsdienu spēlēm nav nepieciešama, jo lielākajā daļā no tām ir iekļautas Tjūringa līdzvērtīgas skriptu valodas, kas spēles gaitā viegli ļauj izstrādāt neizšķiramas mīklas.

Tomēr tas joprojām atstāj daudzas klasikas, kas vēl nav klasificētas.

Šodien Gregs Aloupis no Briseles Brīvās universitātes Beļģijā un pāris draugi aizpilda šo caurumu, vismaz daļēji.

Šie puiši pierāda, ka vairākas klasiskās Nintendo spēles no 80. gadiem ir ļoti sarežģītas. Sarakstā ir iekļauti pirmie trīs Super Mario Bros, Donkey Kong un visu Legend of Zelda spēļu iemiesojumi.

Visas šīs spēles būtībā ir vienādas ar to, ka tās sākas noteiktā punktā ar mērķi sasniegt kādu mērķi. Aloupis un co uzdod šādu jautājumu: vai, ņemot vērā sākuma pozīciju, ir iespējams sasniegt mērķi?

Ja ir grūti izlemt pat šo jautājumu, tad noteikti ir grūti atrast optimālo ceļu, viņi saka.

Šajā kontekstā viņi turpina parādīt, ka visas spēles būtībā ir versijas citai problēmai, ko sauc par 3-SAT, kas, kā zināms, ir NP pilnīga. Šeit ir jāparāda, ka 3SAT noteiktos apstākļos samazina līdz šīm problēmām, tādējādi pierādot, ka tās ir NP grūti.

Tātad, ja jūsu jaunība bija nepareizi pavadīta, spēlējot Super Mario Bros, Donkey Kong vai kādu citu spēli, ko šie puiši pierāda NP-Hard, tad, zinot, cik smagi viņi patiesībā bija, varētu sniegt nelielu mierinājumu, ka jūs netērējat savu laiku. Tad atkal droši vien nē!

Atsauce: arxiv.org/abs/1203.1895 : Klasiskās Nintendo spēles ir (NP-)grūtas

paslēpties