ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 12.02.2021
Просмотров: 192
Скачиваний: 1
Взаимоотношения
между
классами
P
и
NP.
Вопрос
о
взаимоотношении
классов
P
и
NP
имеет
фундаментальное
значение
для
теории
NP-
полных
задач
.
Одно
соотношение
,
которое
неявно
присутствовало
в
проводившихся
ранее
рассуждениях
,
но
до
настоящего
времени
явно
не
формулировалось
,
заключается
в
том
,
что
NP
P
⊆
.
Всякая
задача
распознавания
,
разрешимая
за
полиномиальное
время
детерминированным
алгоритмом
,
разрешима
также
за
полиномиальное
время
недетерминированным
алгоритмом
.
Чтобы
убедиться
в
этом
,
достаточно
заметить
,
что
любой
детерминированный
алгоритм
может
быть
использован
в
качестве
стадии
проверки
недетерминированного
алгоритма
.
Из
проводившихся
ранее
рассуждений
можно
понять
,
что
есть
много
причин
считать
это
включение
строгим
,
т
.
е
.
считать
,
что
P
не
совпадает
с
NP.
Полиномиальные
недетерминированные
алгоритмы
определенно
оказываются
более
мощными
,
чем
полиномиальные
детерминированные
алгоритмы
,
и
не
известны
общие
методы
их
превращения
в
детерминированные
полиномиальные
алгоритмы
.
Способность
недетерминированного
алгоритма
проверить
за
полиномиальное
время
экспоненциальное
число
возможностей
может
навести
на
мысль
,
полиномиальные
недетерминированные
алгоритмы
являются
более
мощным
средством
,
чем
полиномиальные
детерминированные
алгоритмы
.