Сложность вычислений

1. Сложность вычислений

2.

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

3.

По
определению
язык
полуразрешим,
если
существует такая машина Тьюринга T, что
.
Теорема. Существуют полуразрешимые языки,
которые не могут быть разрешимы никаким
алгоритмом.
Примеры. 1. Язык
Н = {(s,х) | <s>(х) останавливается}
(Halting problem – задача об остановке
алгоритма).
2. Язык множества теорем ИП.

4.

Если язык L рассматривается как кодировка
массовой задачи (или проблемы) P, то задача P
называется разрешимой, если язык L является
разрешимым языком, и неразрешимой в
противном случае.
Пример проблемы.
Является ли выполнимой формула алгебра
высказываний?

5.

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

6.

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

7.

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

8.

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

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

10.

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

11.

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