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

Применение практики к теории (Григорий Ярославцев)
Computer Science семинар


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

Описание

Каким образом прогресс в области вычислительной техники может помочь теории сложности и теории алгоритмов? Будет дан краткий обзор существующих работ, которые использовали вычислительную технику для решения задач в теории вычислительной сложности и в теории алгоритмов. Будет неформально описано, как программы для решения задачи линейного программирования могут быть использованы для улучшения нижних оценок для задачи выполнимости. Также будет рассказано о программе исследований для развития нашего понимания схемной сложности. Доклад основан на статье Райана Вильямса “Applying Practice to Theory”. Также будет рассказано о нахождении эффективных булевых схем с использованием SAT–солверов, то есть о реализации программы, предложенной в этой статье.