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