Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Высказывание.docx
Скачиваний:
4
Добавлен:
01.04.2025
Размер:
1 Мб
Скачать
☆

Полиномиальные сведения

Основной метод доказательства того, что проблему P2 нельзя решить за полиномиальное время (т.е. P2P ) состоит в сведении к ней за полиномиальное время такой проблемы P1, что P1P . Такое преобразование языков называется полиномиальным сведением.

Определение. Говорят, что язык является NP-трудным, если для любого языка из класса NP существует полиномиальное сведение языка к языку

Определение. Говорят, что язык является NP-полным, если он принадлежит классу NP и является NP-трудным.

Теорема 1. Если проблема P1 является NP-трудной и существует полиномиальное сведение проблемы P1 к проблеме P2 , то проблема P2 также NP-трудна.

Следствие. Если проблема P1 является NP-полной и существует полиномиальное сведение проблемы P1 к проблеме P2NP , то проблема P2 также NP-полна.

Теоретический результат.

Если некоторая NP-трудная проблема принадлежит классу P , то выполняется равенство P =NP.

Первая NP-полная проблема

Проблема выполнимости (ВЫП) булевых многочленов состоит в следующем

  • выяснить, выполним ли данный булев многочлен?

Теорема Кука. Проблема ВЫП NP-полна.

Ограниченная проблема выполнимости (3ВЫП) булевых многочленов состоит в следующем

  • выяснить, выполнима ли данная КНФ с дизъюнктами из 3 литер?

Проблема выполнимости (ВКНФ) булевых многочленов состоит в следующем

  • выяснить, выполним ли данный булев многочлен в форме КНФ?

Теорема. Проблема ВЫП полиномиально сводится к проблемам 3ВЫП и ВКНФ.

Следствие. Проблемы 3ВЫП и ВКНФ NP-полны.

Основные NP-полные проблемы

Форма описания NP-полной проблемы:

  1. Название проблемы и ее аббревиатура.

  2. Вход проблемы: что и каким образом представляют данные.

  3. Искомый выход: при каких условиях выходом будет «да».

  4. Известная проблема, сведение которой к данной проблеме доказывает NP-полноту последней.

Проблема независимого множества (НМ):

Вход: граф и нижняя граница k, удовлетворяющая условию

Выход: ответ «да» тогда и только тогда, когда G имеет независимое множество из k вершин.

Проблема, сводящаяся к данной: Проблема 3ВЫП.

Следствие. Проблема НМ NP-полна.

Проблема вершинного покрытия (ВП):

Вход: граф и нижняя граница k, удовлетворяющая условию

Выход: ответ «да» тогда и только тогда, когда G имеет вершинное покрытие из k или менее числа вершин.

Проблема, сводящаяся к данной: Проблема НМ.

Следствие. Проблема ВП NP-полна.

Проблема ориентированного гамильтонова цикла (ОГЦ):

Вход: ориентированный граф

Выход: ответ «да» тогда и только тогда, когда G имеет ориентированный гамильтонов цикл.

Проблема, сводящаяся к данной: Проблема 3ВЫП.

Следствие. Проблема ОГЦ NP-полна.

Проблема гамильтонова цикла (ГЦ):

Вход: неориентированный граф

Выход: ответ «да» тогда и только тогда, когда G имеет гамильтонов цикл.

Проблема, сводящаяся к данной: Проблема ОГЦ.

Следствие. Проблема ГЦ NP-полна.

Проблема коммивояжера (ПКОМ):

Вход: взвешенный граф и предельное значение k.

Выход: ответ «да» тогда и только тогда, когда G имеет гамильтонов цикл веса не превышающего k.

Проблема, сводящаяся к данной: Проблема ГЦ.

Следствие. Проблема ПКОМ NP-полна.