Лекция 14_2гр

1. Вычислимость: разрешимые и полуразрешимые языки

2.

Распознавательная
задача
формулируется
следующим универсальным образом:
имеется множество слов
над некоторым
алфавитом и определенный язык
требуется
найти эффективную процедуру (т.е. алгоритм), с
помощью которой для любого слова
можно
определить
или
.

3.

Определение 1. Язык L называется разрешимым
(или рекурсивным), если существует такая машина
Тьюринга T, что для любого слова
выполняются
условия:
1) если
, то при входе w машина T попадает в
заключительное состояние, останавливается и выдает
значение
2) если
, то при входе w машина T попадает в
заключительное состояние, останавливается и выдает
значение
Такие машины соответствуют понятию «алгоритма»
и применяются при решении распознавательных задач
типа «да/нет».

4.

Множество всех разрешимых языков будем
обозначать R (от Recursive)
Свойства: дополнения, конечные пересечения
и конечные объединения разрешимых языков
являются разрешимыми языками.

5.

Определение
2.
Язык
L
называется
полуразрешимым
или
перечислимым,
если
существует такая машина Тьюринга T, что
1) при входе
машина T попадает в
заключительное состояние, останавливается и
выдает значение
,
2) при входе
машина Тьюринга T не дает
никакого результата.
Множество всех полуразрешимых языков будем
обозначать RE (от Recursive Enumerable).

6.

Лемма. Существуют языки, не являющиеся
полуразрешимыми.
Основная
полуразрешимые
теорема.
Существуют
неразрешимые
языки,
т.е.
полуразрешимые языки, которые не могут быть
разрешимы никаким алгоритмом, т.е. выполняется
свойство R
RE.

7.

Классификация
распознавательных
задач
определяется классификацией кодирующих эти
задачи языков.
Определение
называется
3.
Распознавательная
разрешимой
задача
(соответственно,
полуразрешимой), если разрешим (соответственно,
полуразрешим) кодирующий эту задачу язык.

8.

Главные примеры.
1.
Распознавательная
задача
ВЫП
(SАТ)
выполнимости формулы алгебры высказываний
разрешима (с помощью алгоритма составления
истинностных таблиц).
2. Распознавательная задача ТЕОРЕМА (THM)
доказуемости
формулы
полуразрешима
(с
алгебры
помощью
формул), но не разрешима.
предикатов
понятия
вывода

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

10.

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

11.

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

12.

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

13.

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

14.

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

15.

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

16.

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

17.

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

18.

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

20.

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

21.

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

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

23.

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

24.

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

25.

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

26.

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

27.

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

28.

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

29.

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

30.

31.

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

32.

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

33.

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

34.

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

35.

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