#матлог #учёба #семинар #не_мехмат #ВШЭ

Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.

Семинар пройдет в очном формате с одновременной трансляцией
на Математическом факультете ВШЭ, в аудитории 110 (ул. Усачева, д. 6). Мы будем транслировать доклад в zoom, но лучше приходите очно.
Если вам нужен пропуск в здание матфака, пришлите ваши ФИО и просьбу о пропуске на почту kudinov.andrey@gmail.com.

Дата и время: 30.01.2026 в 16:20

Докладчик: Анна Оверчук

Название: Модели вычисления и их сложность. Классические, вероятностные, квантовые.

Аннотация:
Хорошо известна одна из проблем тысячелетия: вопрос о равенстве классов сложности P и NP.
По своей сути, эта проблема, как и многие другие в теории сложности, упирается в сравнение различных математических моделей (концепций) вычислений. На практике оказывается крайне сложно установить строгие соотношения между принципиально разными вычислительными подходами.

В своем докладе я сосредоточусь на сравнении трёх ключевых моделей: классической(машина Тьюринга), вероятностной и квантовой.
Я расскажу о способах их формального определения, обсужу, как их расширяют вероятностные и квантовые подходы, и как сравнивать их вычислительную мощность между собой.

➰ ВК