Pare che dietro ad ogni potenziale matematico si nasconda un potenziale nerd, quasi come se nel tratto di DNA che codifica l'attitudine per le scienze esatte fosse codificata pure l'attrazione per SF, fumetti e videogames (sto certamente parlando anche di me stesso). Le cose si fanno però stimolanti quando al ricercatore riesce di coniugare nerditudine e interesse professionale. È il caso, ad esempio, del buffo saggio The Hardness of the Lemmings Game, or Oh no, more NP-Completeness Proofs (scaricatelo qui), in cui Graham Cormode, professore a Warwick con un resumé lungo così, si dedica seriamente all'analisi di Lemmings, che per chi non lo sapesse è uno dei capisaldi del divertimento videoludico degli anni '90, dove lo scopo del gioco è di prevenire l'estinzione di una torma di creaturine antropomorfe e stupidissime, ispirate idealmente ai simpatici roditori che, almeno a livello di leggende metropolitane, sembrerebbero pericolosamente inclini al suicidio di massa (ci si può giocare qui).
Il punto di vista di Cormode è quello della teoria della complessità computazionale: il problema dell'esistenza di una strategia vincente viene interpretato come problema decisionale, e classificato come tale. L'autore dimostra innanzitutto che si tratta di un problema di classe NP (Nondeterministic Polynomial, cioè tale che una soluzione può essere verificata in tempo polinomiale). Successivamente, per mezzo di una riduzione polinomiale al cosiddetto 3SAT (uno dei problemi NP-hard per antonomasia) si dimostra che l'esistenza di una strategia vincente è a sua volta NP-hard, e di conseguenza NP-completo (classificato cioè tra i più interessanti problemi decisionali, equivalente ad uno dei Millennium Problems della Fondazione Clay).
Nessun commento:
Posta un commento