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

Неприближаемость задачи о покрытии множествами
Вероятностно проверяемые доказательства

Что: Лекция
Когда: Воскресенье, 18 ноября 2012, 13:00–14:35
Где: ПОМИ РАН

Описание

Неприближаемость задачи о покрытии множествами с константным множителем. Конструкция (k,l)-set gadget. Неприближаемость с логарифмическим множителем.