Пятница, 23 октября, комната 106. Начало в 18:00.
Докладчик: Д. Антипов.
Тема: Безусловное разделение классических классов сложности и классов сложности, использующих подсказку.
Abstract
Доклад по статье Harry Buhrman, Lance Fortnow, Rahul Santhanam "Unconditional lower bounds against advice"
В докладе будет доказано, что класс
![$ NEXP $](../../../sites/default/files/tex/41f580b15fcf26cf146a9bb36ecd2fbb16e45200/index.png)
не содержится в
![$ NP/n^c $](../../../sites/default/files/tex/161c0387b5e308a4ba824dfd67a619c09f616138/index.png)
,
![$ MAEXP $](../../../sites/default/files/tex/802b7e8fb325d8d889f9a2efd7e8798080c7b146/index.png)
не содержится в
![$ MA/n^с $](../../../sites/default/files/tex/e93d11c2413a5ac818249d9ded8b6255b8d6e49a/index.png)
и
![$ BPEXP $](../../../sites/default/files/tex/ea66d919531ea49cbdc62f0cfba2f16599dc8001/index.png)
не содержится в
![$ BPP/n^{o(1)} $](../../../sites/default/files/tex/6709d6f09245dc85c2c0db82d1ef04b9630a7a5b/index.png)
. Доказательства этих результатов нерелятивизуемы в отличии от многих других методов, применяющихся в структурной теории сложности.
Также будет построен оракула
![$ A $](../../../sites/default/files/tex/418f8ec9752ec26229a3b82013be4f5d5e563e7a/index.png)
, при котором
![$ EXP^A $](../../../sites/default/files/tex/c95158d97098f5943119c1feea3f27c866207e5e/index.png)
содержится в
![$ ioNP^A $](../../../sites/default/files/tex/51a0ebd906380249ddc06ae77096792a91a0c643/index.png)
.