Наредни састанак Семинара биће одржану петак, 10. маја 2024. године са почетком у сали 301ф Математичког института САНУ са почетком у 12 часова.
Предавач: Александар Прокић, Факултет техничких наука, Универзитет у Новом Саду
Наслов предавања: ПРОБЛЕМ ЗАДОВОЉЕЊА УСЛОВА И ТЕЈЛОР-МИНИМАЛНЕ АЛГЕБРЕ
Апстракт: Проблем задовољења услова (CSP, eng. Constraint Satisfaction Problem) омогућава да опишемо разне комбинаторне проблеме, као и проблеме из свакодневног живота, на сличан начин. Инстанца CSP-а садржи коначан скуп вредности (домен), коначан скуп променљивих и једно питање, да ли се променљивим могу доделити вредности из домена тако да одређени услови буду задовољени. Хипотеза о дихотомији, постављена 90-тих година, гласи да временска сложеност CSP-а је или NP-комплетна или полиномна. Од 2005. године је познато да ако не постоји Тејлорова терм операција компатибилна са релацијама услова онда је временска сложеност NP-комплетна. Хипотезу су доказали Жук и Булатов 2017. године, у независним радовима, тако што су показали да је CSP компатибилан са Тејлоровом операцијом решив у полиномном времену.
На овом предавању ћемо посебну пажњу обратити на Тејлор-минималне алгебре, односно Тејлорове алгебре које немају прави редукт који је Тејлоров. Ове алгебре имају неке лепе особине које немају Тејлорове алгебре у општем случају. Такође ћемо представити како је Булатов дефинисао ивице на „глатким“ алгебрама (његов редукт Тејлорових алгебри), нашу дефиницију ивица над Тејлор-минималним алгебрама, као и везу ивица са апсорбујућим скуповима.
Напомена: Предавања се могу пратити на даљину преко линка:
https://miteam.mi.sanu.ac.rs/call/CihYM6Nratzix7c8G/uJmcdEJs4INWQ8MEoLVzHRGxbfbBEWSBMwXBYcymVoj
Регистрациона форма је доступна на:
https://miteam.mi.sanu.ac.rs/asset/M4zcEwxkzy5PqNS73