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

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

Сведем эту задачу к задаче нахождения MAX-CUT. Сначала найдем бинпоиском величину максимального разреза(ограничение сверху - сумма пропускных способностей всех ребер). Далее буде. Удалять ребра, начиная с ребер самого большого веса. После каждого удаления буде запускать нашу программу с найденным значением MAX-CUT. Если оно изменилось, то удаленное ребро входило в разрез. Указанные операции выполняются за полином. Значит задача из условия лежит в NPC, т.к. она очевидно в NP.



StasFomin (обсуждение) 12:06, 19 мая 2015 (MSK): Не увидел доказательства NP-полноты. Где сведение от известной NP-полной задачи?