• guardie e ladri
• cops and robbers
• grafi
• graphs
• pursuit game
• copnumber
• algorithmic game theory
• teoria algoritmica dei giochi
• combinatorial games
• giochi combinatori

La tesi verte sull'esame di un gioco proposto da Nowakowski e Wintler: si
tratta di una sorta di guardie & ladri (che chiamiamo C&R),
giocato sui nodi di un grafo.

La strategia di questo gioco è stata studiata da diversi autori
che, nel caso deterministico da noi esaminato, forniscono svariate stime
sul numero dei poliziotti (il copnumber) necessari a catturare un ladro
su un determinato grafo, in relazione alla struttura di questo.

E' possibile dimostrare che fissato k, esiste un algoritmo in grado di
determinare in tempo polinomiale se k poliziotti bastano per catturare il
ladro su un dato grafo. Tuttavia, il problema di determinare, in
generale, il copnumber di un grafo dato è decisamente più
complesso, e probabilmente non può essere risolto facendo
affidamento su quelle caratteristiche del grafo che si possono calcolare
in tempo polinomiale.

In questa tesi presento essenzialmente due risultati: la
EXPTIME-completezza del gioco C&R con data posizione iniziale; e la
PSPACE-hardness del gioco C&R quando il ladro possa scegliere la sua
posizione iniziale, ossia la PSPACE-hardness di copnumber.

Il primo di questi risultati, cui è dedicato il terzo capitolo
della tesi, è già stato ottenuto da Goldstein, tuttavia la
mia dimostrazione è differente ed indipendente dalla sua. Il
secondo, che costituisce il quarto capitolo, è, a mio avviso,
nuovo.

Rimane aperto il problema della classificazione precisa della
complessità di copnumber, che come congettura Goldstein,
congetturo anch'io essere EXPTIME-completo. Infatti, il risultato di
PSPACE-hardness esposto nella tesi suggerisce fortemente che il problema
sia, in realtà, EXPTIME-completo (poiché, apparentemante, i
giochi loopy, ossia quelli che ammettono partite di lunghezza infinita,
tendono alla completezza per EXPTIME).