ETD system

Electronic theses and dissertations repository

 

Tesi etd-03292004-094839


Thesis type
Tesi di laurea vecchio ordinamento
Author
Mamino, Marcello
email address
m.mamino@sns.it
URN
etd-03292004-094839
Title
Complessità computazionale di un gioco combinatorio sui grafi
Struttura
SCIENZE MATEMATICHE, FISICHE E NATURALI
Corso di studi
MATEMATICA
Commissione
relatore Berarducci, Alessandro
Parole chiave
  • guardie e ladri
  • cops and robbers
  • grafi
  • graphs
  • pursuit game
  • copnumber
  • algorithmic game theory
  • teoria algoritmica dei giochi
  • combinatorial games
  • giochi combinatori
Data inizio appello
30/03/2004;
Consultabilità
completa
Riassunto analitico
La tesi verte sull&#39;esame di un gioco proposto da Nowakowski e Wintler: si<br>tratta di una sorta di guardie &amp; ladri (che chiamiamo C&amp;R),<br>giocato sui nodi di un grafo.<br><br>La strategia di questo gioco è stata studiata da diversi autori<br>che, nel caso deterministico da noi esaminato, forniscono svariate stime<br>sul numero dei poliziotti (il copnumber) necessari a catturare un ladro<br>su un determinato grafo, in relazione alla struttura di questo.<br><br>E&#39; possibile dimostrare che fissato k, esiste un algoritmo in grado di<br>determinare in tempo polinomiale se k poliziotti bastano per catturare il<br>ladro su un dato grafo. Tuttavia, il problema di determinare, in<br>generale, il copnumber di un grafo dato è decisamente più<br>complesso, e probabilmente non può essere risolto facendo<br>affidamento su quelle caratteristiche del grafo che si possono calcolare<br>in tempo polinomiale.<br><br>In questa tesi presento essenzialmente due risultati: la<br>EXPTIME-completezza del gioco C&amp;R con data posizione iniziale; e la<br>PSPACE-hardness del gioco C&amp;R quando il ladro possa scegliere la sua<br>posizione iniziale, ossia la PSPACE-hardness di copnumber.<br><br>Il primo di questi risultati, cui è dedicato il terzo capitolo<br>della tesi, è già stato ottenuto da Goldstein, tuttavia la<br>mia dimostrazione è differente ed indipendente dalla sua. Il<br>secondo, che costituisce il quarto capitolo, è, a mio avviso,<br>nuovo.<br><br>Rimane aperto il problema della classificazione precisa della<br>complessità di copnumber, che come congettura Goldstein,<br>congetturo anch&#39;io essere EXPTIME-completo. Infatti, il risultato di<br>PSPACE-hardness esposto nella tesi suggerisce fortemente che il problema<br>sia, in realtà, EXPTIME-completo (poiché, apparentemante, i<br>giochi loopy, ossia quelli che ammettono partite di lunghezza infinita,<br>tendono alla completezza per EXPTIME).<br>
File