Город: Тест Санкт-Петербург Новосибирск Казань Язык: Русский English
Что: Лекция
Когда: Воскресенье, 08 марта 2009, 14:00–15:30
Где: ПОМИ РАН

Описание

Нижняя оценка \( ST=\Omega(n^2) \) для зоны \( S \) и времени работы многоленточной машины Тьюринга, распознающей палиндромы. Квадратичная нижняя оценка на время распознавания палиндромов на одноленточной машине Тьюринга. Детерминированная сложность \( D^{best}(f) \) булевой функции \( f \) (минимальная из сложностей \( D(f) \) по всем разбиениям множества входных битов на две равных части). Оценка \( D^{best}(f) \) для функции циклического равенства. Нижняя оценка \( (\sqrt A)T>D^{best}(f) \) для площади \( А \) и времени работы \( T \) микросхемы, вычисляющей булеву функцию \( f \).

Видео