Super Mario Bros Udowodniono NP-Hard

W styczniu przyjrzeliśmy się pracy Giovanniego Viglietty z Uniwersytetu w Pizie we Włoszech, który udowodnił złożoność obliczeniową wielu gier komputerowych z lat 80. i 90., takich jak Pac-Man i Tron.

Viglietta zwróciła uwagę, że ten rodzaj analizy jest niepotrzebny we współczesnych grach, ponieważ większość z nich zawiera ekwiwalentne języki skryptowe Turinga, które z łatwością umożliwiają projektowanie nierozstrzygalnych łamigłówek w ramach rozgrywki.

Jednak to wciąż pozostawia wiele klasyków, które są jeszcze niesklasyfikowane.

Dziś Greg Aloupis z Wolnego Uniwersytetu Brukselskiego w Belgii i kilku kumpli wypełnia tę dziurę, przynajmniej częściowo.

Ci faceci udowadniają, że kilka klasycznych gier Nintendo z lat 80. jest NP-trudnych. Lista zawiera pierwsze trzy wcielenia Super Mario Bros, Donkey Kong i wszystkie gry Legend of Zelda.

Wszystkie te gry są zasadniczo takie same, ponieważ zaczynają się w określonym momencie, aby osiągnąć jakiś cel. Pytanie, które zadają Aloupis i współpracownicy, brzmi: biorąc pod uwagę pozycję wyjściową, czy możliwe jest osiągnięcie celu?

Jeśli nawet na to pytanie trudno jest rozstrzygnąć, to z pewnością trudno jest znaleźć optymalną ścieżkę – mówią.

W tym kontekście pokazują, że wszystkie gry są zasadniczo wersjami innego problemu zwanego 3-SAT, o którym wiadomo, że jest NP-zupełny. Proces tutaj ma pokazać, że 3SAT redukuje się do tych problemów w pewnych okolicznościach, tym samym udowadniając, że są one NP-twarde.

Więc jeśli twoja młodość została zmarnowana, grając w Super Mario Bros, Donkey Kong lub w którąkolwiek z innych gier, ci faceci udowodnili, że są NP-Hard, to wiedza o tym, jak ciężko byli, może zapewnić trochę pocieszenia, że ​​nie marnujesz całkowicie czasu. Z drugiej strony, prawdopodobnie nie!

Nr ref.: arxiv.org/abs/1203.1895 : Klasyczne gry Nintendo są (NP-)Trudne

ukryć