Cтраница 4
VP-полноты задачи о выполнимости необходимо показать, что наличие для нее детерминированного полиномиального алгоритма влечет за собой наличие детерминированного полиномиального алгоритма для любой задачи 5, входящей в NP. Это означает, что 5 полиномиально сводится к задаче о выполнимости. [46]
Имелось также много практически - важных задач, для решения которых, несмотря на все усилия, не были найдены полиномиальные алгоритмы. К первой группе ( полиномиально разрешимых) задач относятся, например, задача выбора ( задача назначения) линейного программирования и задача построения кратчайшего маршрута с заданными концами в графе с заданными длинами дуг. Ко второй группе задач относятся, например, задача коммивояжера, задача о рюкзаке, задача о раскраске. При этом каждая из задач второй группы изучалась - более или менее самостоятельно. [47]
Хотя детальное описание хорошей характеризации является довольно скучным и утомительным занятием, но, располагая такой ха-рактеризацией, мы получаем ключ к построению полиномиального алгоритма выявления свойства эквипаросочетательности графов. [48]
В этой главе мы исследовали множество комбинаторных задач, которые эквивалентны в том смысле, что либо все они могут быть решены детерминированным полиномиальным алгоритмом, либо ни одна из них не может быть решена таким способом ( упр. Класс этих эквивалентных задач широк и включает задачи из разных областей прикладной и чистой математики и исследования операций. В конце раздела мы рассмотрим несколько интересных а - полных и оЛГ - трудных задач, не вошедших в текст или упражнения этой главы. [49]
Очевидно, из существования полиномиального алгоритма решения какой-нибудь NP-трудной задачи следует, что для каждой задачи из класса JT & ( для каждой ЛТ-полпой задачи в том числе) существует полиномиальный алгоритм ее решения. [50]
Следует отметить, что если имеется алгоритм нахождения Т - сое-динения минимального веса в графе с неотрицательными весами, выполняемый за полиномиальное время, то конструкция из предыдущего доказательства приводит к полиномиальному алгоритму для нахождения Т - соединения минимального веса в графе с произвольными весами. Такой алгоритм получается из результатов гл. [51]