Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Порядок закачек — NPC

Материал из DISCOPAL
Перейти к: навигация, поиск

Представим распределенный сервис стриминга видеофильмов. Центральный сервер с полной БД фильмов получает от периферийных кеширующих узлов запросы на требуемые фильмы и ориентировочные сроки, когда люди собираются их посмотреть.

Однако пропускная способность от сервера с дисками к внешнему миру ограничена, и требуется составить работающее расписание отгрузки фильмов.

Конкретно, узел контроля планирования получает n-заданий вида:

  • «начать_не_раньше, закончить_не_позже, размер_фильма»i, 1<=i<=n
  • максимальная пропускная способность не больше МаксКанал

И говорит «OK» (или «Паника-Паника!» в противном случае), если существует такое расписание из n команд отгрузки, соответствующих заданию (1<=i<=n ):

  • «время_начала, время_окончания, ширина_канала»i,
  • время_началаi >= начать_не_раньшеi
  • время окончанияi <= закончить_не_позжеi
  • ширина_каналаi <= МаксКанал
  • ширина_канала*(время_окончания — время_начала)i >= размер_фильмаi

Докажите NP-полноту задачи.

Hint: Можно через «Рюкзак-выполнимость» или «SUBSET-SUM»

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.