Лекция 12_3гр

1. Вычислительная сложность

2.

Целью теории вычислительной сложности является
принципиальная проблема – отделить задачи, которые
могут быть решены за реальное (полиномиальное)
время, от задач, решение которых осуществляется за
практически нереализуемое (экспоненциальное) время.
Примеры: вычисление НОД целых чисел и разложение
на множители целых чисел (для 1000-значного простого
числа требуется 10500 итераций).

3.

Возраст Земли – 1017 секунд.
Площадь земной поверхности - 1018 квадратных
дюймов.
Современный суперкомпьютер выполняет 1016
операций в секунду.
Если на каждом квадратном дюйме разместить
суперкомпьютер и все они работали бы параллельно в
течение всего срока жизни Земли, то они бы выполнили
1051 операций. Это намного меньше, чем 52! (число
способов упорядочивания колоды карт) и 2200 (число
подмножеств 200-элементного множества).

4.

В качестве модели алгоритма рассматривается машина
Тьюринга T, вычисляющая словарную функцию
Временной сложностью машины T называется функция
значение которой равно числу шагов работы машины
T, сделанных при вычислении значения
если
определено, и
не определено, если
не определено.
Ленточной сложностью машины T называется функция
значение которой равно числу ячеек машины T,
используемых при вычислении значения
и
не
определено, если
не определено.

5.

Говорят, что машина Тьюринга T
полиномиальную временную сложность
имеет
k
=n
(или «время работы ограничено полиномом
»),
если, обрабатывая вход
более
длины п, T делает не
переходов и останавливается независимо
от того, допущен вход или нет.
Определение. Говорят, что язык
классу
P,
если
он
разрешим
принадлежит
некоторой
детерминированной машины Тьюринга
полиномиальной временной сложностью.
T
с

6.

Определение.
Распознавательная
задача
принадлежит классу P, если ее язык принадлежит
классу P, т.е. эта задача решается с помощью
полиномиального
алгоритма
детерминированной
машины
-
некоторой
Тьюринга
T
с
полиномиальной временной сложностью.
Пример. Задача вычисления НОД целых чисел
принадлежит классу P.

7.

Помимо детерминированной машины Тьюринга
Т=( ,Q, , q , q ) с одной программой
S
F
в теории
алгоритмов рассматриваются недетерминированные
машины
Тьюринга
программами
Т=( ,Q, 1, 2, q , q )
S
F
с
двумя
1, 2, которая на каждом шаге
вычислений случайным образом выбирает одну из
этих двух программ и по ней выполняет изменение
своей конфигурации.

8.

Определение. Язык
принадлежит классу NP,
если
он
разрешим
некоторой
недетерминированной машины Тьюринга T с
полиномиальной временной сложностью.
Определение.
Распознавательная
задача
принадлежит классу NP, если ее язык
принадлежит классу NP, т.е. эта задача решается с
помощью
полиномиального
недетерминированного алгоритма - некоторой
недетерминированной машины Тьюринга T с
полиномиальной временной сложностью.

9.

Это равносильно тому, что для объектов x данной
задачи имеется полиноминально ограниченный
сертификат
y,
с
помощью
которого
за
полиномиальное время проверяется, что x является
или нет решением данной задачи.
Задача поиска – задача, для которой существует
алгоритм с полиномиальным временем, который
может проверить для полиноминально ограниченных
входных данных, что они являются решением задачи.

10.

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

12.

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

13.

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

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

15.

Форма описания NP-полной проблемы:
Название проблемы и ее аббревиатура.
2. Вход проблемы: что и каким образом
представляют данные.
3. Искомый выход: при каких условиях
выходом будет «да».
4. Известная проблема, сведение которой
к данной проблеме доказывает NP1.
полноту последней.

16.

Проблема выполнимости (ВЫП)
Вход: слова w в алфавите A, кодирующие
формулы алгебры
экземпляры ВЫП.
высказываний
-
Выход: значение 1 - ответ «да» - тогда и
только тогда, когда закодированная
формула
выполнима.
алгебры
высказываний

17.

Проблема выполнимости (ВЫП) формул
алгебры высказываний состоит в следующем
выяснить,
выполнима
ли
данная
формула алгебры высказываний ?
Теорема Кука. Проблема ВЫП NP-полна.

18.

Проблема выполнимости (ВКНФ)
Проблема выполнимости ВКНФ
формул
алгебры высказываний состоит в следующем
выяснить, выполнима ли данная формула
алгебры высказываний в форме КНФ?

19.

Вход проблемы ВКНФ:
слова w в алфавите A, кодирующие формулы
алгебры высказываний в форме КНФ экземпляры ВКНФ.
Искомый выход:
значение 1 - ответ «да» - тогда и только
тогда, когда закодированная формула
алгебры высказываний выполнима.
Известная NP-полная проблема, которая
сводится к ВКНФ – проблема ВЫП.

20.

Лемма. Для любой формулы алгебры логики за
полиномиальное время можно построить такую
формулу алгебры логики в форме КНФ, что
выполняются условия:
1) формула выполнима в том и только том
случае, если выполнима КНФ ;
2) длина формулы линейно зависит от
количества символов в формуле .
Доказательство: в формуле
выражаем
импликации и эквивалентности через конъюнкции,
дизъюнкции и отрицания; затем проносим
отрицания к переменным и, раскрывая скобки в
нужном порядке, получаем формулу в форме
КНФ.

21.

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

22.

Ограниченная проблема выполнимости (3ВЫП)
Ограниченная проблема выполнимости 3ВЫП формул алгебры высказываний состоит в
следующем
выяснить, выполнима ли данная формула
алгебры высказываний в форме КНФ с
дизъюнктами из 3 литер?

23.

Вход проблемы 3-ВЫП:
слова w в алфавите A, кодирующие формулы
алгебры высказываний в форме КНФ с
дизъюнктами из 3 литер - экземпляры ВКНФ.
Искомый выход:
значение 1 - ответ «да» - тогда и только
тогда, когда закодированная формула
выполнима.
Известная NP-полная проблема, которая
сводится к 3-ВЫП – проблема ВКНФ.

24.

Лемма. Для любой формулы алгебры высказываний в
форме КНФ за полиномиальное время можно построить
такую формулу алгебры высказываний в форме
КНФ с дизъюнктами из 3-х литер, что выполняются
условия:
1) формула выполнима в том и только том
случае, если выполнима КНФ ;
2) длина формулы линейно зависит от
количества символов в формуле .
Доказательство:
индукцией по числу символов
операций в дизъюнктах формулы
получаем
формулу в форме КНФ с дизъюнктами из 3-х литер.

25.

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

26.

Проблема независимого множества (НМ):
Вход: граф
и нижняя граница k,
удовлетворяющая условию
Выход: ответ «да» тогда и только тогда,
когда G имеет независимое множество из k
вершин.
Проблема, сводящаяся к данной: Проблема
3-ВЫП.
Следствие. Проблема НМ NP-полна.

27.

28.

Проблема вершинного покрытия (ВП):
Вход: граф
и нижняя граница k,
удовлетворяющая условию
Выход: ответ «да» тогда и только тогда, когда
G имеет вершинное покрытие из k или менее
числа вершин.
Проблема, сводящаяся к данной: Проблема
НМ.
Следствие. Проблема ВП NP-полна.

29.

Проблема ориентированного гамильтонова
цикла (ОГЦ):
Вход: ориентированный граф G.
Выход: ответ «да» тогда и только тогда,
когда
G
имеет
ориентированный
гамильтонов цикл.
Проблема,
сводящаяся
к
данной:
Проблема 3-ВЫП.
Следствие. Проблема ОГЦ NP-полна.

30.

Проблема гамильтонова цикла (ГЦ):
Вход: неориентированный граф G.
Выход: ответ «да» тогда и только тогда, когда
G имеет гамильтонов цикл.
Проблема, сводящаяся к данной: Проблема
ОГЦ.
Следствие. Проблема ГЦ NP-полна.

31.

Проблема коммивояжера (ПКОМ):
Вход: взвешенный граф G и предельное
значение k.
Выход: ответ «да» тогда и только тогда, когда
G имеет гамильтонов цикл веса не
превышающего k.
Проблема, сводящаяся к данной: Проблема
ГЦ.
Следствие. Проблема ПКОМ NP-полна.

32.

Задача целочисленного программирования
(ЗЦП):
Вход: система линейных ограничений,
целевая функция и предельное значение k.
Выход: ответ «да» тогда и только тогда, когда
функция имеет превышающее k значение для
допустимых переменных.
Проблема, сводящаяся к данной: Проблема
3-ВЫП.
Следствие. Проблема ЗЦП NP-полна.