ЛекториумМедиатека
Поиск
Личный кабинет

Вероятностно проверяемые доказательства. Лекция 7

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

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

Страница лекции на сайте Computer Science клуба

Лекции курса

9
  1. Вероятностно проверяемые доказательства. Лекция 1
  2. Вероятностно проверяемые доказательства. Лекция 2
  3. Вероятностно проверяемые доказательства. Лекция 3
  4. Вероятностно проверяемые доказательства. Лекция 4
  5. Вероятностно проверяемые доказательства. Лекция 5
  6. Вероятностно проверяемые доказательства. Лекция 6
  7. Вероятностно проверяемые доказательства. Лекция 7▶ Вы тут
  8. Вероятностно проверяемые доказательства. Лекция 8
  9. Вероятностно проверяемые доказательства. Лекция 9

Онлайн-курсы по программированию

3