ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 13.02.2021
Просмотров: 134
Скачиваний: 1
Недетерминированное
вычисление
и
класс
NP.
Рассмотрим
задачу
КОММИВОЯЖЕР
,
описание
которой
приведено
было
ранее
.
В
условии
даны
:
множество
городов
,
расстояния
между
ними
и
граница
B;
при
этом
спрашивается
,
существует
ли
проходящий
через
все
города
маршрут
длины
,
не
превосходящей
B.
Полиномиальный
алгоритм
решения
этой
задачи
не
известен
.
Предположим
,
однако
,
что
относительно
некоторой
индивидуальной
задачи
кто
-
то
получил
ответ
“
да
”.
Если
вы
в
этом
сомневаетесь
,
то
можно
потребовать
“
доказательства
”
этого
утверждения
–
предъявление
маршрута
,
обладающего
необходимыми
свойствами
.
Имея
предъявленное
решение
,
нетрудно
проверить
,
является
ли
оно
на
самом
деле
маршрутом
,
и
если
это
так
,
то
вычислить
.
Его
длину
,
сравнить
ее
с
границей
B
и
тем
самым
проверить
соответствующее
утверждение
.
Более
того
,
эту
“
процедур
проверки
”
можно
представить
в
виде
алгоритма
,
временная
сложность
которого
ограничена
полиномом
от
Length
[
I
].
Именно
понятие
полиномиальной
“
проверяемости
”
позволяет
выделить
задачи
класса
NP
.
Отметим
,
что
проверяемость
за
полиномиальное
время
не
влечет
разрешимости
за
полиномиальное
время
.
А
именно
,
утверждая
,
что
за
полиномиальное
время
можно
проверить
ответ
“
да
”
для
задачи
КОММИВОЯЖЕР
,
мы
не
учитываем
время
,
которое
может
понадобиться
на
поиск
нужного
маршрута
среди
экспоненциального
числа
всех
возможных
маршрутов
.
Мы
лишь
утверждаем
,
что
по
любому
заданному
маршруту
для
индивидуальной
задачи
I
можно
за
полиномиальное
время
проверить
,
“
доказывает
”
ли
этот
маршрут
,
что
ответ
на
вопрос
относительно
индивидуальной
задачи
I
есть
“
да
”.
Неформально
класс
NP
можно
определить
с
помощью
понятия
,
которое
мы
будем
называть
недетерминированным
алгоритмом
.
Такой
алгоритм
состоит
из
двух
различных
стадий
–
стадии
угадывания
и
стадии
проверки
.
По
заданной
индивидуальной
задаче
I
на
первой
стадии
происходит
просто
“
угадывание
”
некоторой
структуры
S
.
Затем
I
и
S
вместе
подаются
в
качестве
входа
на
стадию
проверки
,
которая
выполняется
обычным
детерминированным
образом
и
либо
заканчивается
ответом
“
да
”,
либо
заканчивается
ответом
“
нет
”,
либо
продолжается
бесконечно
без
остановки
.
Класс
NP
,
определяемый
неформально
, -
это
класс
всех
задач
распознавания
П
,
которые
при
разумном
кодировании
могут
быть
решены
недетерминированными
(
N
- nondeterministic)
алгоритмами
за
полиномиальное
(
P
- polynomial)
время
.
Пример
,
приведенный
выше
,
показывает
,
что
задача
КОММИВОЯЖЕР
принадлежит
NP
.
Имеется
еще
одно
важное
отличие
“
решения
”
задачи
распознавания
недетерминированным
алгоритмом
от
решения
детерминированным
алгоритмом
,
а
именно
в
первом
случае
отсутствует
симметрия
между
ответами
“
да
”
и
”
нет
”.
Если
задача
: “
Дано
I
;
верно
ли
что
для
I
выполняется
свойство
X
?”
может
быть
решена
полиномиальным
(
детерминированным
)
алгоритмом
,
то
такое
же
утверждение
справедливо
и
для
дополнительной
задачи
; “
Дано
I
,
верно
ли
,
что
для
I
не
выполняется
свойство
X
?”.
Совершенно
не
очевидно
,
что
то
же
самое
верно
для
всех
задач
,
разрешимых
за
полиномиальное
время
недетерминированными
алгоритмами
.
Рассмотрим
,
например
,
дополнение
задачи
КОММИВОЯЖЕР
:
дано
множество
городов
,
расстояния
между
ними
и
граница
B
;
верно
ли
,
что
нет
маршрута
,
проходящего
через
все
города
и
имеющего
длину
,
не
превосходящую
B
?
Для
выяснения
,
имеет
ли
поставленный
вопрос
ответ
“
да
”,
не
известен
способ
,
который
был
бы
короче
,
чем
проверка
всех
(
или
почти
всех
)
возможных
маршрутов
.
Другими
словами
,
не
известен
полиномиальный
недетерминированный
алгоритм
решения
этой
дополнительной
задачи
.
Та
же
самая
ситуация
имеет
место
для
многих
других
задач
из
NP
.
Таким
образом
,
принадлежность
задачи
П
классу
P
влечет
принадлежность
дополнительной
задачи
классу
P
,
но
не
известно
,
имеет
ли
место
аналогичное
утверждение
для
класса
NP
.
