Laboratory of Mathematical Logic at PDMI

Пятница, 22 сентября, комната 106. Начало в 16:00.

Докладчик: С. Николенко.

Тема: Связи между дерандомизацией, сложностью в среднем и в наихудшем случае.

Abstract

Доклад по статье Dan Gutfreund, Amnon Ta-Shma ``New connections between derandomization, worst-case complexity and average-case complexity''

В работе показано, что из достаточно мягкого предположения о дерандомизации и worst-case сложности (NP не равно RP) вытекает, что существует язык, сложный для BPP в среднем и вычислимый за недетерминированное квазиполиномиальное время.

Доказательство основано на деталях доказательств из работ Impagliazzo, Levin ``No better ways to generate hard NP instances than picking uniformly at random'' и Gutfreund, Shaltiel, Ta-Shma ``If NP-languages are hard in the worst-case then it is easy to find their hard instances''.