Ricerc@Sapienza

Il nostro obiettivo è studiare le soluzioni efficienti di problemi computazionali da un punto di vista più organico possibile. Lo studio ha tre parti: (1) determiniamo limiti inferiori all'efficienza delle soluzioni utilizzando una combinazione dei metodi della complessità computazionale e della proof theory; (2) progettiamo algoritmi per la soluzione di problemi su grafi computazionalmente complessi; (3) sviluppiamo algoritmi sperimentalmente efficienti per la risoluzione di problemi caratterizzati da istanze di taglia estremamente elevate (big data), anche mediante un approccio distribuito.

Per il primo punto partiamo da problemi specifici, e.g. soddisfacibilità nella logica proposizionale (satisfiability), colorazione di grafi, ricerca di clique, per poi studiare le performance di algoritmi. L'intenzione è di dimostrare limitazioni inferiori all'efficienza senza fare uso di assunzioni non dimostrate (come invece si fa nella teoria dell'NP-completezza), ma studiando la "proof complexity". Essenzialmente analizzeremo l'efficienza di algoritmi per grafi e dimostreremo matematicamente che non sono efficienti.

Per il secondo punto si studieranno problemi su grafi di complessità elevata, come ad esempio la sensibilità del massimo flusso rispetto a variazioni della capacità di archi, e altre generalizzazioni che presentano complessità computazionali quadratiche, o comunque superlineari, rispetto alla dimensione del grafo, e problemi nell'ambito della Formal Concept Analysis

Per il terzo punto il progetto si concentrerà su particolari categorie di problemi, particolarmente studiate in ambito bioinformatico, che hanno come scopo quello di confrontare due o più sequenze di caratteri allo scopo di determinarne la similarità. Ci si concentrerà in particolare su algoritmi di tipo alignment-free, che consentono di stimare il grado di similarità di due sequenze in un tempo subquadratico rispetto alla taglia delle stesse.