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

Первые оценки на формульную сложность.
Сложность булевых функций


Что: Семинар
Когда: Среда, 22 февраля 2017, 18:30–19:50
Где: ПОМИ РАН

Описание

В первой части доклада будут рассмотрены оценки, связывающие глубину и размер формул с гейтами входной степени 2 и с гейтами произвольной входной степени. Во второй части будет доказана квадратичная нижняя оценка на размер формул с гейтами входной степени 2.