Pac-Man Proved NP-Hard By Computational Complexity Theory
The classic '80s arcade game turns out to be equivalent to the travelling salesman problem, according a new analysis of the computational complexity of video games http://www.technologyreview.com/blog/arxiv/27528/
apl13
Сокобан, кстати, тоже.
apl13
Интересно, что они под "Троном" понимают в этой статье? Мотоциклы?
Lord456
Pac-Man Proved NP-Hard By Computational Complexity TheoryThe classic '80s arcade game turns out to be equivalent to the travelling salesman problem, according a new analysis of the computational complexity of video games
http://www.technologyreview.com/blog/arxiv/27528/