Studentski seminar, 10. maj 2024.

Naredni sastanak Seminara biće održanu petak, 10. maja 2024. godine sa početkom u sali 301f Matematičkog instituta SANU sa početkom u 12 časova.
 
Predavač: Aleksandar Prokić, Fakultet tehničkih nauka, Univerzitet u Novom Sadu

Naslov predavanja: PROBLEM ZADOVOLjENjA USLOVA I TEJLOR-MINIMALNE ALGEBRE

Apstrakt:
Problem zadovoljenja uslova (CSP, eng. Constraint Satisfaction Problem) omogućava da opišemo razne kombinatorne probleme, kao i probleme iz svakodnevnog života, na sličan način. Instanca CPS-a sadrži konačan skup vrednosti (domen), konačan skup promenljivih i jedno pitanje, da li se promenljivim mogu dodeliti vrednosti iz domena tako da određeni uslovi budu zadovoljeni. Hipoteza o dihotomiji, postavljena 90-tih godina, glasi da vremenska složenost CSP-a je ili NP-kompletna ili polinomna. Od 2005. godine je poznato da ako ne postoji Tejlorova term operacija kompatibilna sa relacijama uslova onda je vremenska složenost NP-kompletna. Hipotezu su dokazali Žuk i Bulatov 2017. godine, u nezavisnim radovima, tako što su pokazali da je CSP kompatibilan sa Tejlorovom operacijom rešiv u polinomnom vremenu.

Na ovom predavanju ćemo posebnu pažnju obratiti na Tejlor-minimalne algebre, odnosno Tejlorove algebre koje nemaju pravi redukt koji je Tejlorov. Ove algebre imaju neke lepe osobine koje nemaju Tejlorove algebre u opštem slučaju. Takođe ćemo predstaviti kako je Bulatov definisao ivice na "glatkim" algebrama (njegov redukt Tejlorovih algebri), našu definiciju ivica nad Tejlor-minimalnim algebrama, kao i vezu ivica sa apsorbujućim skupovima.

Napomena: Predavanja se mogu pratiti na daljinu preko linka:
https://miteam.mi.sanu.ac.rs/call/CihYM6Nratzix7c8G/uJmcdEJs4INWQ8MEoLVzHRGxbfbBEWSBMwXBYcymVoj

Registraciona forma je dostupna na:
https://miteam.mi.sanu.ac.rs/asset/M4zcEwxkzy5PqNS73


 Ostavite vaš komentar 

Komentari(0)

Nažalost nije moguće ostaviti komentar.