P = NP с точностью до переиспользования (Павел Соколов)
Семинар международной лаборатории теоретической информатики ФКН
Просто типизированное лямбда-исчисление — минимальный формальный язык, интересный с точки зрения теории языков программирования. Мы докажем, что нормальную форму любого терма этого языка можно вычислить за полиномиальное число переиспользуемых редукций. В качестве простого следствия мы получим, что P = NP «с точностью до переиспользования».
Выступает Павел Соколов, стажер-исследователь международной лаборатории теоретической информатики ФКН ВШЭ.
26 июня 2025
Международная лаборатория теоретической информатики: https://cs.hse.ru/big-data/tcs-lab/
ФКН: https://cs.hse.ru
Подписывайтесь на нас:
📍 https://vk.com/cshse
📍 https://t.me/fcs_hse
📍 https://t.me/sci_fcs