Прошел семинар "P = NP с точностью до переиспользования"

Соколов Павел, стажер-исследователь международной лаборатории теоретической информатики, выступил с докладом "P = NP с точностью до переиспользования" на семинаре лаборатории

МЛ ТИ

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

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