ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 13.02.2021
Просмотров: 141
Скачиваний: 1
NP -
полные
задачи
Пока
теоретики
продолжают
поиск
более
мощных
методов
доказательства
труднорешаемости
задач
,
параллельно
ведутся
работы
по
сравнению
сложности
различных
задач
.
Как
уже
было
сказано
ранее
,
обнаружение
таких
взаимосвязей
между
задачами
часто
может
дать
разработчику
алгоритмов
полезную
информацию
.
Основной
метод
,
используемый
для
доказательства
того
,
что
две
задачи
близки
,
состоит
в
"
сведении
"
их
друг
к
другу
с
помощью
конструктивного
преобразования
,
которое
отображает
любую
индивидуальную
задачу
первого
типа
в
эквивалентную
и
индивидуальную
задачу
второго
типа
.
Такое
преобразование
позволяет
превратить
любой
алгоритм
решения
второй
задачи
соответствующий
алгоритм
решения
первой
задачи
.
Фундамент
теории
NP-
полных
задач
был
заложен
в
работе
С
.
Кука
,
опубликованной
в
1971
г
.
под
названием
"
Сложность
процедур
вывода
теорем
".
В
этой
короткой
,
но
элегантной
работе
Кук
получил
несколько
важных
результатов
.
Во
-
первых
,
он
подчеркнул
важность
понятия
"
сводимость
за
полиномиальное
время
",
т
.
е
.
сводимость
,
которая
выполняется
с
помощью
алгоритма
с
полиномиальной
временной
сложностью
.
Если
одна
задача
сводится
за
полиномиальное
время
к
другой
,
то
любой
полиномиальный
алгоритм
решения
второй
задачи
может
быть
превращен
в
полиномиальный
алгоритм
решения
первой
.
Во
-
вторых
,
он
обратил
внимание
на
класс
задач
распознавания
свойств
(
класс
NP),
которые
могут
быть
решены
за
полиномиальное
время
на
недетерминированном
вычислительном
устройстве
. (
Задачей
распознавания
свойств
называется
задача
,
решениями
которой
могут
быть
либо
"
да
",
либо
"
нет
".)
Большинство
не
поддающихся
решению
задач
,
которые
встречаются
на
практике
,
после
переформулировки
их
в
виде
задач
распознавания
попадают
в
этот
класс
.
В
-
третьих
,
С
.
Кук
доказал
,
что
одна
конкретная
задача
из
NP,
называемая
задачей
о
выполнимости
,
обладает
тем
свойством
,
что
всякая
другая
задача
из
класса
NP
может
быть
сведена
к
ней
за
полиномиальное
время
').
Таким
образом
,
если
задача
о
выполнимости
может
быть
решена
за
полиномиальное
время
,
то
и
любая
задача
из
класса
NP
полиномиально
разрешима
,
а
если
какая
-
то
задача
из
NP
труднорешаема
,
то
и
задача
о
выполнимости
также
должна
быть
труднорешаемой
Таким
образом
,
в
некотором
смысле
задача
о
выполнимости
- "
самая
трудная
"
в
классе
NP.
Наконец
,
С
.
Кук
предположил
,
что
и
другие
задачи
из
класса
NP
могут
быть
,
аналогично
задаче
о
выполнимости
,
самыми
''
трудными
"
представителями
класса
NP.
Вслед
за
этим
Р
.
Карп
опубликовал
ряд
результатов
,
из
которых
следует
,
что
многие
хорошо
известные
комбинаторные
задачи
,
включая
задачу
о
коммивояжере
,
будучи
сформулированы
в
виде
задачи
распознавания
,
столь
же
"
трудны
",
как
задача
о
выполнимости
.
Позднее
относительно
широкого
круга
других
задач
было
доказано
,
что
они
по
трудности
эквивалентны
этим
задачам
,
а
сам
класс
эквивалентности
,
состоящий
из
''
самых
трудных
"
задач
из
NP,
получил
название
"
класс
NP-
полных
задач
".
Оригинальные
идеи
Кука
оказались
удивительно
плодотворными
.
Они
позволили
свести
много
разнообразных
вопросов
о
сложности
в
единый
вопрос
:
"
Верно
ли
,
что
NP-
полные
задачи
труднорешаемы
?".
Список
,
таких
задач
,
содержит
сотни
различных
задач
, NP-
полнота
которых
уже
установлена
.
По
мере
того
как
все
больше
и
больше
задач
,
представляющих
интерес
с
разных
точек
зрения
,
попадают
в
этот
класс
эквивалентности
,
его
важность
постоянно
возрастает
.
Вопрос
о
том
,
действительно
ли
NP-
полные
задачи
труднорешаемы
,
в
настоящее
время
считается
одним
из
основных
открытых
вопросов
современной
математики
и
теоретической
кибернетики
.
Вопреки
готовности
большинства
специалистов
считать
,
что
все
NP-
полные
задачи
труднорешаемы
,
прогресс
как
в
доказательстве
,
так
и
в
опровержении
этого
далеко
идущего
предположения
весьма
незначителен
.
Однако
,
несмотря
на
отсутствие
доказательства
того
,
что
из
NP-
полноты
следует
труднорешаемость
, NP-
полнота
задачи
означает
,
что
для
ее
решения
полиномиальным
алгоритмом
требуется
,
по
крайней
мере
,
крупное
открытие
.
