Complessità Computazionale: dai Problemi Classici ai Giochi Carta-e-Penna

Lo studio della complessità computazionale permette di suddividere i problemi tra quelli risolvibili in tempo alpiù polinomiale rispetto alla dimensione dell'istanza, e quelli computazionalmente intrattabili, dei quali cioè non si hanno a disposizione algoritmi risolutivi efficaci; tra questi rientrano i problemi NP-completi, ovvero i più difficili tra i problemi verificabili in tempo polinomiale, ed i problemi ASP-completi, nozione che prende in considerazione, oltre all'esistenza di soluzioni, anche il numero di esse. La teoria della complessità computazionale è ad oggi focalizzata sull'irrisolta questione dell'inclusione tra le classi P e NP, e lo studio di esempi pratici di problemi NP- e ASP-completi potrebbe suggerire nuove prospettive dalle quali affrontare tale questione dai notevoli risvolti economici per quanto riguarda l'utilizzo di software e procedure risolutive di molti problemi. Le nozioni teoriche della complessità computazionale sono in questo lavoro applicate alla dimostrazione dell'intrattabilità di problemi legati all'algebra booleana, primo tra tutti il problema di soddisfattibilità di espressioni booleane (mediante il Teorema di Cook-Levin) e poi la sua restrizione 3-SAT. Vengono trattati inoltre problemi legati alla teoria dei grafi, in particolare grafi euleriani (polinomialmente risolvibili) ed hamiltoniani (ASP-completi) mediante le varianti 3-HAM e MAX3-HAM, e problemi con applicazioni pratiche quali il problema del Commesso Viaggiatore e 3-dimensional Matching. L'ultima parte è invece dedicata all'analisi di alcuni giochi carta-e-penna: Nonogram (la cui NP-completezza segue da 3-dimensional Matching), Slither Link (la cui ASP-completezza segue da MAX3-HAM), e Erbivori. Quest'ultimo, che rappresenta un caso particolare di `tiling problem', deve la sua ASP-completezza ad una riduzione a partire dalla trasposizione grafica di SAT, denominata Circuit-SAT, e costituisce un contributo inedito all'elenco dei problemi NP- ed ASP-completi.