Il Problema della Dualità degli Ipergrafi

Il presente elaborato ha come obiettivo l’analisi e la collocazione formale del problema complementare a DUAL, il problema della dualità degli ipergrafi, all’interno della classe di complessità GC(log(n)^2, TC^0). Per dimostrare questo risultato, è stata adottata una procedura basata sul modello di calcolo non deterministico, nota come guess and check, formalizzato nell’algoritmo ND-NotDUAL. Questo problema stabilisce se un ipergrafo H non sia il duale di un ipergrafo G. L’attenzione dell’elaborato è rivolta alla ricerca di un new transversal di G rispetto a H, condizione sufficiente alla non dualità. Tuttavia, l’algoritmo ND-NotDUAL non cerca concretamente un new transversal, ma una prova della sua esistenza, ovvero un testimone doppio della non dualità di G e H. La prima fase non deterministica consiste nella scelta di un certificato di prova Σ, un insieme di etichette di piccola dimensione (O(log^2(n)) bits di memoria, dove n è la taglia dell’input). La seconda fase deterministica esegue una serie di controlli volti alla verifica della non dualità degli ipergrafi forniti in input. Si è dimostrato che tali controlli possono essere espressi in logica del primo ordine con quantificatori di conteggio (FO(COUNT)). Ciò permette di collocare la fase di check nella classe di complessità TC^0. Unendo questi due risultati, si ottiene la classificazione finale del problema, collocandolo in GC(log^2(n), TC^0).