Семинар Международной лаборатории теоретической информатики: О свойствах замкнутости задач подсчёта
В четверг, 20 июня , приглашаем вас с 18:10 до 19:30 на семинар лаборатории ТИ в аудитории R407, Покровский бульвар, 11.
Название доклада: О свойствах замкнутости задач подсчёта
Докладчик: Ярослав Иванашев
Аннотация:
Класс#P состоит из функций, которые равны количеству принимающих путей некоторой недетерминированной полиномиальной машины Тьюринга. Эти функции соответствуют количеству решений задач из класса NP. В докладе будет доказано следующее утверждение: класс#P замкнут относительно композиции с классом FP (т. е. FP ◦#P ⊆#P) тогда и только тогда, когда класс#P совпадает со своим подклассом UFP.