Complessità dei programmi 2-ASP(Q) con vincoli deboli

Un nuovo articolo su arXiv (2605.27338) studia 2-ASP(Q)^w, un frammento di ASP(Q) che estende l'Answer Set Programming con quantificatori e vincoli deboli. Questa classe può esprimere problemi di ottimizzazione fino a Delta_3^P. Lo studio fornisce una caratterizzazione completa della complessità per i principali compiti computazionali, inclusi casi precedentemente non affrontati. Sul lato pratico, gli autori introducono nuove strategie per calcolare insiemi di risposta quantificati ottimali nel sistema Casper utilizzando una tecnica di raffinamento astratto guidato da controesempi (CEGAR). La valutazione sperimentale su benchmark difficili mostra l'efficacia.