logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-03292004-094839


Tipo di tesi
Tesi di laurea vecchio ordinamento
Autore
Mamino, Marcello
Indirizzo email
m.mamino@sns.it
URN
etd-03292004-094839
Titolo
Complessità computazionale di un gioco combinatorio sui grafi
Dipartimento
SCIENZE MATEMATICHE, FISICHE E NATURALI
Corso di studi
MATEMATICA
Relatori
relatore Berarducci, Alessandro
Parole chiave
  • algorithmic game theory
  • combinatorial games
  • copnumber
  • cops and robbers
  • giochi combinatori
  • grafi
  • graphs
  • guardie e ladri
  • pursuit game
  • teoria algoritmica dei giochi
Data inizio appello
30/03/2004
Consultabilità
Completa
Riassunto
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).
File