- •Логика высказываний.
- •Логическая равносильность формул.
- •Нормальные формы формул алгебры высказываний.
- •Метод резолюций в алгебре высказываний
- •Алгебра логических значений
- •Булевы многочлены и булевы функции
- •Системы булевых функций
- •Логика предикатов Понятие предиката
- •Переключательные схемы
- •Минимизация булевых многочленов
- •Алгебра предикатов
- •Формулы алгебры предикатов
- •Если , – формулы, то формулами являются также выражения
- •Интерпретации формул алгебры предикатов
- •Тавтологии алгебры предикатов
- •Логическая равносильность формул алгебры предикатов
- •Логическое следование формул алгебры предикатов
- •Формальные исчисления
- •Исчисление высказываний
- •Исчисление предикатов
- •Аксиоматические теории первого порядка
- •Интерпретация теории первого порядка
- •Выполнимость формул теории первого порядка
- •Примеры теорий первого порядка
- •Свойства теорий первого порядка
- •Проблема общезначимости формул алгебры предикатов
- •Метод семантических таблиц
- •Автоматическое доказательство теорем
- •Нормальные формы для формул алгебры предикатов
- •Метод резолюций в исчислении предикатов
- •Элементы теории алгоритмов
- •Характерные особенности моделей вычислений Общие понятия алгоритма и вычислимой функции.
- •Формальные грамматики
- •Нормальные алгорифмы Маркова
- •Рекурсивные функции
- •Машины Тьюринга
- •Сложность вычислений
- •Сложность алгоритмов
- •Полиномиальные сведения
Полиномиальные сведения
Основной метод доказательства того, что проблему 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-полной проблемы:
Название проблемы и ее аббревиатура.
Вход проблемы: что и каким образом представляют данные.
Искомый выход: при каких условиях выходом будет «да».
Известная проблема, сведение которой к данной проблеме доказывает NP-полноту последней.
Проблема независимого множества (НМ):
Вход:
граф
и
нижняя граница k,
удовлетворяющая
условию
Выход: ответ «да» тогда и только тогда, когда G имеет независимое множество из k вершин.
Проблема, сводящаяся к данной: Проблема 3ВЫП.
Следствие. Проблема НМ NP-полна.
Проблема вершинного покрытия (ВП):
Вход:
граф
и
нижняя граница k,
удовлетворяющая
условию
Выход: ответ «да» тогда и только тогда, когда G имеет вершинное покрытие из k или менее числа вершин.
Проблема, сводящаяся к данной: Проблема НМ.
Следствие. Проблема ВП NP-полна.
Проблема ориентированного гамильтонова цикла (ОГЦ):
Вход:
ориентированный
граф
Выход: ответ «да» тогда и только тогда, когда G имеет ориентированный гамильтонов цикл.
Проблема, сводящаяся к данной: Проблема 3ВЫП.
Следствие. Проблема ОГЦ NP-полна.
Проблема гамильтонова цикла (ГЦ):
Вход: неориентированный граф
Выход: ответ «да» тогда и только тогда, когда G имеет гамильтонов цикл.
Проблема, сводящаяся к данной: Проблема ОГЦ.
Следствие. Проблема ГЦ NP-полна.
Проблема коммивояжера (ПКОМ):
Вход:
взвешенный
граф
и предельное значение k.
Выход: ответ «да» тогда и только тогда, когда G имеет гамильтонов цикл веса не превышающего k.
Проблема, сводящаяся к данной: Проблема ГЦ.
Следствие. Проблема ПКОМ NP-полна.
