Что: | Лекция |
Когда: | Воскресенье, 08 марта 2009, 10:25–11:55 |
Где: | ПОМИ РАН |
Вероятностная сложность предиката \( GT \): верхние оценки \( R^{pub}_{\epsilon}(GT)=O(\log n \log\log n) \) и \( R_{\epsilon}(GT)=O(\log n) \). Верхняя оценка безошибочной вероятностной сложности для функции \( DISJ_{\log n} \): \( R_{0}(DISJ_{\log n})=O(\log n) \).