Seminario - Funzioni submodulari e Valued Constraint Satisfaction Problems su domini infiniti

il giorno 4 Maggio alle 15,30 in aula Anile, la Dott.ssa Caterina Viola (Università di Dresda) terra' un seminario dal titolo:
Funzioni submodulari e Valued Constraint Satisfaction Problems su domini infiniti

Abstract: I Valued Constraint Satisfaction Problems (VCSP) sono una vasta classe di ottimizzazione combinatoria. Si vuole classificare la complessita` computazionale dei VCSP in base alla natura del linguaggio, ovvero dell'insieme (finito) di funzioni di costo in input.
Recentemente, la complessita` computazionale dei VCSP per linguaggi su domini finiti e` stata classificata in tal senso. Dopo una breve introduzione alla teoria della complessita` computazionale e agli strumenti algebrici usati per lo studio della complessita` dei VCSP, presentero` il mio lavoro che inizia l'investigazione dei VCSP su domini infiniti studiando, in particolare, la complessita` dei VCSP per funzioni di costo lineari a tratti omogenee, ovvero quelle funzioni che ammettono una definizione nella logica del primo ordine sull'insieme dei numeri razionali, Q, usando la (usuale) relazione di ordine (<) , l'identita` di Q (1) e la moltiplicazione per scalari in Q.
Mostrero` che tali VCSP possono essere risolti in tempo polinomiale quando le funzioni di costo sono anche submodulari. In particolare, per le funzioni lineari a tratti omogee la submodularita` e` una condizione di trattabilita` massimale: aggiungendo al linguanggio una funzione non submodulare il problema diventa NP-hard.