Home

Семинар 27 апреля 2007 года

Пятница, 27 апреля, комната 106. Начало в 15:30.

Докладчик: А. Куликов.

Тема: Миникурс по сложности формул и схем. Четвертая лекция.

Abstract

В четвертой (заключительной) лекции миникурса мы узнаем основные идеи доказательства наилучшей известной нижней оценки $ n^3 $ на размер формулы.

Ключевыми моментами доказательства являются оценка на уменьшение формулы при случайной подстановке и использование функции Андреева.

НИКАКИХ ПРЕДВАРИТЕЛЬНЫХ ЗНАНИЙ НЕ ТРЕБУЕТСЯ (определение сложности формулы при необходимости будет повторено).