Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Линейные нижние оценки на схемы без ограничений и метод элиминации гейтов (А. Куликов)
Сложность булевых функций


Что: Лекция
Когда: Воскресенье, 02 октября 2011, 11:15–12:50
Где: ПОМИ РАН
Слайды: boolean_functions_complexity_lecture_021011.pdf

Описание

Основная идея метода элиминации гейтов. Примеры свойств функций, использующихся в доказательстве верхних оценок: \( 2n \) для функций, имеющих хотя бы три различные подфункции относительно любых двух переменных; \( 2n \) для функции индексации; \( 7n/3 \) для функций высокой степени.

Материалы

Приложенные файлы