* Originally in ESP.JUEGOS
* Crossposted in ESP.MSX
* Crossposted in ESP.8Y16BITS

­Hola All!


Nunca me lo había planteado así, la verdad. ¿Cómo lo veis?


+--------------------------------------------------------------------+
| Análisis de complejidad de videojuegos clásicos |
| http://barrapunto.com/article.pl?sid=12/01/26/2350247 | +--------------------------------------------------------------------+

En [0]Slashdot se hacen eco de que Giovanni Viglietta, investigador
italiano de la Universidad de Pisa, ha [1]publicado un estudio donde
analiza la complejidad teórica de 13 videojuegos clásicos. Para calcular
la complejidad temporal y/o espacial, se basa en reducir los casos a equivalentes a selección de [2]caminos hamiltonianos ([3]NP-completo), determinar la complejidad espacial a partir de compuertas e
interruptores, etc. Entran dentro de la complejidad temporal [4]NP-hard: Boulder Dash, Lemmings, Lode Runner, Pac-Man, Pipe Mania, Puzzle Bobble
3, Starcraft, y Tron ([5]PSPACE-completo). Por otro lado, dentro de
complejidad espacial, serían [6]PSPACE-hard: Doom y Prince of Persia.

Discute esta historia en:
http://barrapunto.com/comments.pl?sid=12/01/26/2350247

Enlaces:
0. http://games.slashdot.org/story/12/01/26/238244/pac-man-is-np-hard
1. http://arxiv.org/abs/1201.4995
2. http://es.wikipedia.org/wiki/Camino_hamiltoniano
3. http://es.wikipedia.org/wiki/NP-completo
4. http://es.wikipedia.org/wiki/NP-hard
5. http://es.wikipedia.org/wiki/PSPACE-completo
6. http://es.wikipedia.org/wiki/PSPACE


-
A reveure!!
Enric
__________________________________________________________________
FidoNet: 2:343/107.1 | beholderbbs.org | fidonet.cat | .es | .ws
InterNet: kishpa(at)kishpa(dot)com | kishpa.com | GPG#0xDCCB8CFC

... Hasta el rabo, todo es toro.
--- crashmail + golded + binkd
* Origin: Black flag & crossed bones : Eye Of The Beholder BBS! (2:343/107.1)