What: | Lecture |
When: | Sunday, 02 October 2011, 11:15–12:50 |
Where: | ПОМИ РАН |
Slides: | boolean_functions_complexity_lecture_021011.pdf |
Основная идея метода элиминации гейтов. Примеры свойств функций, использующихся в доказательстве верхних оценок: \( 2n \) для функций, имеющих хотя бы три различные подфункции относительно любых двух переменных; \( 2n \) для функции индексации; \( 7n/3 \) для функций высокой степени.