QuoteToday, Giovanni Viglietta at the University if Pisa in Italy reveals a body of Herculean work in this area in which he classifies a large number of games from the 1980s and 90s including Pac-Man, Doom, Tron and many others.
Vigliettas work involves several steps. The first is to determine the class of computational complexity to which the game belongs. Next, he works out whether knowing how to solve the game also allows you to solve many other problems in the same class, a property that complexity theorists call hardness. Finally, he determines whether the game is complete, meaning that it is one of the hardest in its class.
His approach is relatively straightforward. He first works through a number of proofs showing that…
( THIS IS A SUMMARY OF THE POST. CLICK THE TITLE TO READ THE REST AND JOIN THE DISCUSSION )