Полиномиальные сводимости и 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»
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.