Проблема - выполнимость
Cтраница 2
Доказательство Кука было основано на понятии сводимости, которое мы упоминали ранее, когда говорили о теории вычислимости. Он показал, что всякий частный случай задачи из NP может быть преобразован в соответствующий случай проблемы выполнимости таким образом, что оба они одновременно или имеют, или не имеют решения. Более того, это преобразование может быть выполнено за полиномиальное время. Другими словами, проблема выполнимости является достаточно общей для фиксации структуры любой задачи из NP. Отсюда следует, что если бы мы умели решить проблему выполнимости за полиномиальное время, то мы сумели бы построить алгоритм, работающий полиномиальное время, для любой задачи из NP. [16]
 |
Задача о коммивояжере за полиномиальное время сводима к проблеме выполнимости. [17] |
Я решил исследовать, являются ли некоторые классические комбинаторные задачи, которые издавна считались практически невыполнимыми, архетипическими в смысле Кука. Я назвал такие задачи полиномиально полными, но этот термин был вытеснен более точным термином NP-полные. Задача NP-полна если она лежит в классе NP и всякая задача из NP полиномиально сводима к ней. Таким образом, по теореме Кука проблема выполнимости NP-полна. Для доказательства того, что задача из NP является NP-полной, достаточно показать, что некоторая задача, NP-полнота которой доказана, полиномиально сводима к данной задаче. Построением серии полиномиальных по времени сведений я показал, что большинство классических задач упаковки, покрытия, паросочетания, разбиения, выбора маршрутов и составления расписаний, которые возникают в комбинаторной оптимизации, NP-полны. [18]
Доказательство Кука было основано на понятии сводимости, которое мы упоминали ранее, когда говорили о теории вычислимости. Он показал, что всякий частный случай задачи из NP может быть преобразован в соответствующий случай проблемы выполнимости таким образом, что оба они одновременно или имеют, или не имеют решения. Более того, это преобразование может быть выполнено за полиномиальное время. Другими словами, проблема выполнимости является достаточно общей для фиксации структуры любой задачи из NP. Отсюда следует, что если бы мы умели решить проблему выполнимости за полиномиальное время, то мы сумели бы построить алгоритм, работающий полиномиальное время, для любой задачи из NP. [19]
Страницы: 1 2