经典任天堂游戏是NP-Hard

[guest]

感谢Karen Millen Sale的投递
新闻来源:Solidot
科学家最近对视频游戏的计算复杂度产生了浓厚兴趣，发表了一系列相关论文。最新的论文由布鲁塞尔自由大学与MIT计算机科学和人工智能实验室的科学家发表在预印本网站上，他们发现许多经典游戏都包含一个NP-Hard问题，例如一些关卡要求玩家在正确的时间按键，要达到完美通关十分困难。

研究结果发现，任天堂的经典游戏：Mario、Donkey Kong、Legend of Zelda、Metroid和Pokemon复杂度都是NP-Hard，Super Mario Bros1、3和Lost Levels、Super Mario World、除Zelda II: The Adventure of Link之外的塞尔达传说系列等游戏也都适用于该结果。