Home

Пятница, 23 октября, 18:00, к. 106

Пятница, 23 октября, комната 106. Начало в 18:00.

Докладчик: Д. Антипов.

Тема: Безусловное разделение классических классов сложности и классов сложности, использующих подсказку.

Abstract

Доклад по статье Harry Buhrman, Lance Fortnow, Rahul Santhanam "Unconditional lower bounds against advice"

В докладе будет доказано, что класс $ NEXP $ не содержится в $ NP/n^c $, $ MAEXP $ не содержится в $ MA/n^с $ и $ BPEXP $ не содержится в $ BPP/n^{o(1)} $. Доказательства этих результатов нерелятивизуемы в отличии от многих других методов, применяющихся в структурной теории сложности.
Также будет построен оракула $ A $, при котором $ EXP^A $ содержится в $ ioNP^A $.