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

Суперполиномиальная нижняя оценка для монотонных формул (Александр Куликов)
Computer Science семинар


Что: Лекция
Когда: Воскресенье, 15 марта 2009, 16:20–17:50
Где: ПОМИ РАН

Описание

Доказательство нижних оценок на размер схем, вычисляющих булевы функции, является одной из самых известных и трудных задач Theoretical Computer Science. Несложно показать, что количество функций от n переменных сильно больше количества схем, имеющих полиномиальный от n размер, из чего следует, что большинство функций вычисляются только схемами экспоненциального размера. Несмотря на это, лучшая известная на данный момент нижняя оценка на схемную сложность есть 3n. Суперполиномиальные нижние оценки, однако, были доказаны для ограниченных схем: Й. Хастад привёл пример функции, не вычислимой схемами полиномиального размера константной глубины, А. А. Разборов доказал суперполиномиальную нижнюю оценку для монотонных схем. В данном докладе мы приведём элегантное доказательство А. А. Разборова суперполиномиальной нижней оценки для монотонных формул (в формулах, в отличие от схем, выходная степень каждого гейта равна единице). Данное доказательство опирается на теорему Карчмера–Вигдерсона, связывающую глубину схем с коммуникационной сложностью некоторой игры, а также использует некоторые свойства графов Пэли.