Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Порядок закачек — NPC
Представим распределенный сервис стриминга видеофильмов. Центральный сервер с полной БД фильмов получает от периферийных кеширующих узлов запросы на требуемые фильмы и ориентировочные сроки, когда люди собираются их посмотреть.
Однако пропускная способность от сервера с дисками к внешнему миру ограничена, и требуется составить работающее расписание отгрузки фильмов.
Конкретно, узел контроля планирования получает n-заданий вида:
- «начать_не_раньше, закончить_не_позже, размер_фильма»i, 1<=i<=n
- максимальная пропускная способность не больше МаксКанал
И говорит «OK» (или «Паника-Паника!» в противном случае), если существует такое расписание из n команд отгрузки, соответствующих заданию (1<=i<=n ):
- «время_начала, время_окончания, ширина_канала»i,
- время_началаi >= начать_не_раньшеi
- время окончанияi <= закончить_не_позжеi
- ширина_каналаi <= МаксКанал
- ширина_канала*(время_окончания — время_начала)i >= размер_фильмаi
Докажите NP-полноту задачи.
Hint: Можно через «Рюкзак-выполнимость» или «SUBSET-SUM»
решение, предложенное Дыкало Андреем
Как известно, задача «разбиения» на два равных по весу множества NP-полная. Возможность сведения задачи «разбиения» к задаче «мультипотоковое расписание», сформулированной в условии, означает NP-полноту второй задачи.
Сведение:
Пусть на входе задачи «разбиение» мы имеем n-натуральных чисел, интерпретируемых как веса предметов: A={a(1),a(2),..,a(n)}.
Обозначение: C=0.5 * [Σi {a(i) + (a(i)+1 mod 2)} + (Σi {a(i) + (a(i)+1 mod 2)} + 1 mod 2)]. (Четное число)
Для каждого i-ого предмета составим систему ограничений, i из {1,2,3,..,n}:
начать_не_раньше(i) = 1;
закончить_не_позже(i) = C;
размер_фильма(i) = a(i) + (a(i)+1 mod 2); (Если четное, то прибавить 1, иначе - прибавить 0.)
Далее, если Σi {a(i) + (a(i)+1 mod 2)} - нечетная, то добавим еще один фильм размера 1.
Определение
C=0.5 * [Σi {a(i) + (a(i)+1 mod 2)} + (Σi {a(i) + (a(i)+1 mod 2)} + 1 mod 2)]
вынесло мне мозг, но насколько я понял, для
входа 4,6,8,2 мы получим [5,7,9,3], а С=½*(12+16)=14. ???Получили условия задачи о расписании. Дополним их заданием «МаксКанал»:
МаксКанал = 2;
Таким образом, вход задачи о «разбиении» полиномиально сведен ко входу задачи о расписании, т. к. каждому предмету соответствует O(1) операций формирования условия задачи о расписании.
Доказательства однозначности ответов:
Утверждение 1: Если расписание существует, то ни одна из загрузок не осуществляется с шириной_канала = МаксКанал = 2.
Пусть при сформулированных условиях задачи о расписании нашлось расписание
такое, что хотя бы одна загрузка производится с шириной канала 2.
Пусть номер этой загрузки 1 (предположил, не умаляя общности). В силу
условий преобразования входов задачи все загрузки имеют нечетный размер.
На закачку номер 1 выделена ширина 2 и время t(1) >= (a(1) + [a(1)
mod 2])/2 + 1. Время на закачки
T >= t(1) + ({a(2)+[a(2)+1mod2]}+{a(3)+[a(3)+1mod2]}+...+{a(n)+[a(n)+1mod2]})/2 > C. Таким образом, T>C, но T<=C.
Получили противоречие, доказывающее справедливость утверждения.
Вопрос задачи: существует ли расписание такое, что все загрузки осуществляемы им?
Или формально с учетом УТВЕРЖДЕНИЯ 1: существует ли разбиение задач на два
множества таких, что суммарное время на выполнение каждого множества задач не превосходит С.
Или аналитически:
Существует ли S—подмножество весов A, удовлетворяющее условию:
max{ΣSa{i}, ΣA/Sa{i}} <= C.
Утверждение 2: если выполняется max{Σs a{i}, ΣA/S a{i}} <= 0.5 * ΣA a(i), то ΣS a{i} = ΣA/Sa{i}.
Доказательство:
x = Σsa{i}, z = ΣA/Sa{i}, C = 0.5 * ΣA a(i), тогда
z = 2C — x
неравенство переписывается в виде:
max{x, 2C-x} <= C оно имеет единственное решение при x = C.
То есть если решение существует, то существует S и Σs a{i} = ΣA/S a{i}.
Таким образом, если ответ задачи «расписания» ДА, то и ответ задачи «разбиение» ДА.
Если же ответ первой «НЕТ», то не существует такого множества S, для которого
выполняется: Σs a{i} = ΣA/S a{i}.
Ч.Т.Д.
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.