СЪЮЗ НА МАТЕМАТИЦИТЕ В БЪЛГАРИЯ
ИНСТИТУТ ПО МАТЕМАТИКА И ИНФОРМАТИКА – БАН
НАЦИОНАЛЕН КОЛОКВИУМ ПО МАТЕМАТИКА
Поредната сбирка на Колоквиума ще се състои на 14 юли 2021 г. (сряда) от 16:15 часа
в Заседателната зала на ИМИ – БАН, София, ул. „Акад. Г. Бончев“, блок 8, и онлайн.
Доклад на тема:
Колко е трудно да се докаже сложност?
От теорията на изчислителната сложност до алгебричната комбинаторика и обратно
ще изнесе проф. Грета Панова, Университет на Южна Калифорния, САЩ.
Абстракт. Колко е сложно да се реши дадена задача? А колко е трудно да се докаже, че една задача е сложна?
Отговорите на такива въпроси можем да намерим в теорията на изчислителната сложност, където водещият проблем, P vs NP, е за разграничаването на двата основни класа на сложност. Алгебричният вариант е VP vs VNP, с който се занимава геометричната теория за изчислителна сложност (GCT). Използвайки методи от алгебричната комбинаторика, ние опровергаваме една от основните хипотези на GCT и така показваме, че разграничаването на VP и VNP е по-непосилна задача от очакваното.
В този доклад аз ще обясня основните понятие и идеи от тези теории и ще покажа връзките с алгебра и комбинаторика. Ще покажем и обратната връзка, как теорията на изчислителната сложност може да се приложи в алгебрични и комбинаторни проблеми.
Zoom Meeting https://us02web.zoom.us/j/85767399108?pwd=TGR3YkR6d1NCYWtoSVM4QjIvcVN4UT09
Meeting ID: 857 6739 9108
Passcode: 044702
Поканват са всички интересуващи се.
Заседанието ще се проведе при спазване на противоепидемичните мерки.