Laboratory of Mathematical Logic at PDMI

Пятница, 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$.