Leírás
Az algebrai dinamikus programozás elmélete azon az észrevételen alapszik, hogy minden dinamikus programozás valamely matematikai/kombinatorikai objektumok halmazán értelmezett multiplikatív függvényt összegez az értelmezési tartomány valamely részhalmazán. Az értelmezési tartomány bizonyos részhalmazai rekurzívan felépíthetőek. Ezek a rekurziók univerzális algoritmusokat biztosítanak, amelyek univerzálisak abban az értelemben, hogy különböző számítási problémák (pl. optimalizálás, leszámlálás, létezés eldöntése) ugyanazzal a szorzásokat és összeadásokat tartalmazó rekurzióval számolhatóak ki, csak mindig a számítási problémának megfelelő félgyűrűket kell a számolás közben alkalmazni. Például a fent említett optimalizálási, leszámlálási és eldöntési problémák esetén az alkalmazandó félgyűrűk rendre a tropikus félgyűrű, a természetes számok félgyűrűje, illetve a Boole félgyűrű.
A dinamikus programozás univerzális abban az értelemben is, hogy ugyanahhoz a számítási problémához mindig ugyanazt a félgyűrűt kell alkalmazni, függetlenül attól, hogy milyen matematikai/kombinatorikai objektumokat milyen rekurzióval építünk fel közben. Így van értelme azt vizsgálni, hogy milyen számítási problémákhoz léteznek alkalmas félgyűrűk. Az előadásban két nem-triviális félgyűrűt mutatok be, amelyeket rendre additív függévnyek összegére és általánosabban eloszlások momentumainak a kiszámolására valamint Pareto optimalizálásra lehet használni. Mindkét esetben nyílt kérdés a további általánosítás lehetősége, valamint az, hogy algebrai eszközökkel milyen bonyolultságelméletet lehet felépíteni.