Семинар МЛ ТИ: "О проверке выполнимости алгебраических формул над полем из двух элементов"
В среду, 14 июня, приглашаем Вас на семинар лаборатории теоретической информатики.
Семинар пройдет онлайн с 18:10 до 19:30.
Название доклада: О проверке выполнимости алгебраических формул над полем из двух элементов
Докладчик: Михаил Николаевич Вялый
Аннотация:
Будет рассказано о вероятностном полиномиальном алгоритме проверки выполнимости алгебраических формул глубины 3 над полем из двух элементов, верхней операцией в которых является сложение. Алгоритм с теми же характеристиками существует для проверки равенства нулю многочлена (задача PIT), задаваемого формулами указанного вида. Однако эти задачи и алгоритмы их решения существенно отличаются. Вероятностный алгоритм для PIT основан на лемме Шварца-Зиппеля, а алгоритм проверки выполнимости основан на лемме Вельянта- Вазирани.