С. Капулкин (АФТУ)
Иерархия по времени вычислений с подсказкой

Доклад по статье Melkebeek, Pervyshev "A Generic Time Hierarchy for Semantic Models With One Bit of Advice". В докладе будет рассмотрена иерархия по времени для семантических классов с подсказкой. Будет дано достаточно общее определение семантического класса, включающее в себя такие классы, как RP, BPP, AM и другие. Будет сформулирована и доказана следующая теорема:
Для любой разумной семантической модели вычислений и любых констант a и c найдется язык, вычислимый за полиномиальное время с одним битом подсказки, но не за время $\$n^c\$\; с\; \$a\$$ битами подсказки.