Семинар МЛ ТИ "P = NP с точностью до переиспользования"

Дата: 26 июня 2025 г., 18:10 - 19:30

Докладчик: Соколов Павел, стажер-исследователь международной лаборатории теоретической информатики

Аннотация: Просто типизированное лямбда-исчисление — минимальный формальный язык, интересный с точки зрения теории языков программирования. Мы докажем, что нормальную форму любого терма этого языка можно вычислить за полиномиальное число переиспользуемых редукций. В качестве простого следствия мы получим, что P = NP "с точностью до переиспользования".

Место проведения: ​​​​Zoom 

Идентификатор конференции: 826 1434 3196
Код доступа: 770870