Теорема об отсутствии верхней границы сложности вычислений

Теорема 1: О не существовании верхней границы сложности вычисления.

Для любой общерекурсивной функции (с помощью которой пытаемся ограничить сложность) существует общерекурсивная 0,1-функция такая что существует значение для которого справедливо

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

 

Теорема 2: О существовании сложновычислимой функции.

Для любой общерекурсивной функции существует общерекурсивная функция с коротким ответом (0, 1) такая что существует значение , такое что выполняется условие при всех т.е.:

1) Для всех x кроме конечного числа точек

2) Сложность вычисления которой будет почти во всех точках x т.е. почти для всех x.

 

Теорема Блюма о линейном ускорении

Теорема 3: Теорема Блюма.

Для любой общерекурсивной функции существует общерекурсивная функция с коротким ответом (0, 1) такая что для любой машины вычисляющей f(x) найдется машина вычисляющая f(x) такая что

Рассмотрим следствия этой теоремы:

1. Пусть существует функция и тогда существует функция f(x) которая допускает вычисление со сложность причём в свою очередь для справедливо выражение

Т.е. существует босконечная последовательность машин

Таким образом не существует нижней границы сложности вычисления. Существуют задачи которые всегда можно ускорить.

2. Пусть существует функция и есть процессор который совершает 1 шаг за 1 нс, тогда общее время выполнения программы будет

Возьмём более быстрый процессор, который будет совершать 2 шага за 1 нс, тогда общее время выполнения программы на новом процессоре будет

Используем новый алгоритм решения и запустим его на первом процессоре, тогда общее время выполнения программы будет , т.е.

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

 

Сложность массовой проблемы

Каждая массовая проблема может быть решена на определенной машине Тьюринга. Пусть имеется массовая задача , характеризуемая множеством параметров, - индивидуальная задача, в которой эти параметры фиксированы. Пусть с массовой задачей связана и зафиксирована схема кодирования , которая ставит каждой индивидуальной задаче в соответствие слово в некотором алфавите . При этом размером задачи понимается длинна машинного слова

- погружение индивидуальной массовой проблемы во внешний алфавит.

Если индивидуальная задача имеет решение, МТ будет иметь вид:

Схема кодировки - способ погружение массовой проблемы в алфавит.

Сложность задачи можно охарактеризовать функциями сложности:

1. , где - временная сложность по худшему случаю, -длина машинного слова.

2. , где - емкостная асимптотическая сложность, -длина машинного слова.

Возможно ли оценить нижнюю границу сложности?

Существуют методы прямого получения нижних оценок. Пример: метод следов.

Методом следов можно определить сложность следующих задач:

1. Является ли произвольное слово p - симметричным.

2. Является ли P декартовым квадратом

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

Выделяют следующие классы сложности

1. Класс p – полиноминальная сложность. Говорят, что машина Т решает задачу за полиноминальное время, если существует многочлен, который аппроксимирует сложность массовой проблемы . Если задача решается за полиноминальное время, то она принадлежит классу р.

2. Класс Е. В противном случае говорят, что машина Т решает задачу за экспоненциальное время - экспоненциальная сложность задачи.

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

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

Практическая значимость класса P

Какую задачу можно решить при заданной скорости быстродействия

Функция временной сложности	Размер решаемой Задачи на ЭВМ	Размер решаемой Задачи на ЭВМ	Размер решаемой Задачи на ЭВМ

 

Для того, чтобы решать задачи больших размерностей мы либо увеличиваем время, либо увеличиваем производительность.

Из таблицы видно, что полиноминальные алгоритмы лучше реагируют на увеличение размерности задач, а любой экспоненциальный алгоритм, начиная с некоторой размерности, оказывается практически не решаемым. Это означает, что при не решаем сейчас, а также не решаем в обозримом будущем. Если полиноминальный алгоритм не решаем сейчас, то его можно будет решить в обозримом будущем.

Вывод: полиноминальная задача - легко решаемая, экспоненциальная задача – трудно решаемая.

Свойства класса P полиноминальных задач:

1. Класс P одинаков для всех разумных алгоритмических моделей (ЧРФ, машины поста и т. д.)

2. Схема кодирования является существенной при выделении класса P. При изменении схем кодировки задача может стать экспоненциальной. Поэтому нужно обязательно указывать схему кодировки.

3. Класс P является замкнутым – можно комбинировать полиноминальные алгоритмы, используя один в качестве «подпрограммы» другого и при этом результирующий алгоритм будет полиноминальным. .

Примеры лёгкорешаемых и труднорешаемых задач

Пусть имеется множество

1. Поиск наибольшего элемента

2. Упорядочивание элементов в порядке возрастания . Имеется алгоритм порядка - каждый элемент нужно сравнить с каждым.

3. Установление является ли отношение на множестве отношением эквивалентности. Задачу зададим матрицей ,где Для того, чтобы отношение M являлось отношением эквивалентности необходимо выполнение условий: Для решения задачи необходимо проверить условий. Сложность задачи

4. Проверка является ли отношение на множестве гамильтоновым. Бинарное отношение является гамильтоновым, если элементы можно так упорядочить , что выполнено соотношение . В настоящее время неизвестно полиноминального алгоритма проверки гамильтоновости произвольного отношения . Тривиальный алгоритм требует упорядочивований .

5. Задача выполнимости КНФ. Пусть имеется формула от булевых переменных в некотором фиксированном базисе . Пусть формула имеет конъюнктивную нормальную форму, т. е. имеет вид где , если переменна присутствует в КНФ в составе элементарной дизъюнкции и , если переменной нет. Входными данными в эту задачу является . Задача состоит в чтобы определить существует ли такой набор значений для , при котором . На настоящий момент не известно полиноминального алгоритма решения этой задачи. Тривиальный алгоритм предполагает проверку всех возможных значений , т. е. требует перебора наборов значений переменных и вычисления для каждого такого набора значения формулы .

Определим теперь класс задач распознавания, т. е. имеющих ответ «ДА» или «НЕТ». . Для того, чтобы задача содержалась в классе требуется только, чтобы в случае, если имеет ответ «Да», то существует слово , длины, ограниченной полиномом от размера такое, что задача с начальными данными , принадлежит . Слово называется удостоверением или догадкой для задачи. .

Для каждой задачи распознавания можно определить соответствующую задачу удостоверения .

Примеры задач удостоверения:

1. Имеет ли уравнение для набора коэффициентов решение в целых числах. Доказательство существования решение – предъявление этого решения:

2. Пусть дана задача проверки гамильтоновости бинарного отношения. Если R – гамильтоново отношение, то удостоверением этого будет последовательность элементов - конкретный набор номеров элементов для которого выполняется свойство гамильтоновсти.

3. Пусть дана задача проверки выполнимости КНФ. Если - выполнимая формула, то удостоверением будет соответствующий выполняющий набор .

Хотя задачи 2 и 3 решается за экспоненциальное время, соответствующие им задачи удостоверения решается за полиноминальное время.

 

Класс «NP»

 

Класс определяется через понятие недетерменированного алгоритма. Введем понятие недетерминированной машины Тьюринга (машина с оракулом).

 

x

x

*

 

 

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

существует слово-догадка такое, что через конечное число шагов остановится с ответом «Да».

Сложность НТ: , где - сложность работы УМ (длина слова -догадки), - сложность решения детерминированного алгоритма.

Сложность вводится только в том случае, когда соответствующая задача распознавания имеет ответ «Да», иначе сложность не определена.

Чтобы задача принадлежала классу необходимо, чтобы сложность НТ была полиноминальной:

 

Свойства класса NP:

1. существует алгоритм, который позволяет решить эту задачу со сложностью , где p – некоторый полином. Существует НТ, . Всего может быть записано , где k – мощность внешнего алфавита задачи, . Для каждой из догадок существует такой , что через шагов НТ остановится в позиции , либо вообще не остановится проделав шагов если мы пришли в положение - ответ «Да», иначе переходим к новому слову. Если она не остановилась ни для одного слова, то ответ будет «Нет». . Мы должны перебрать все полиномы, чтобы создать перечисление многочленов в рамках которого должны достигнуть каждый полином за полиноминальное время.

 

*

x

x

x

К -слов

KK - слов

 

 

Для одного слова К просматриваем один такт работы. Для 2 –х слов KKпросматриваем два такта работы. Если слово занимает одну ячейку смотрим остановится ли машина Тьюринга за один такт Если слово занимает две ячейки смотрим остановится ли машина Тьюринга за 2 такта.

2. Класс однозначно определяется относительно всех разумных алгоритмических моделей.

3. Класс инвариантен относительно обратной задачи: А вот для класса это не так: Пример: Если проверка выполнимости КНФ решается за полиноминальное время. Для того, чтобы убедится что КНФ не выполнима полиноминальной догадки не существует.

 

Как соотносятся классы и ?

подкласс (Стоит отметить,что не любой класс это множество, хотя любое множество это класс. В данном случае эти понятия совпадают.)

Существует много фактов, что , - маловероятно. Если , то (дополнение класса до ) - трудно решаемые задачи.