Математическая логика и теория алгоритмов. Стенюшкина В.А. - 70 стр.

      Имеет место теорема: Пусть а ≥ 1, b> 1 – константа, f(n) – функция и ре-
куррентное соотношение Т(n)=аТ(n/b)+f(n), где под n/b понимается одно из
двух ближайших целых чисел. Тогда:
      -для f(n)=O(nlogbа-ε), ε>0 верно, что Т(n)=Θ(nlogbа);
      -для f(n)=Θ(nlogbа) верно, что Т(n)=Θ(nlogbа log(n));
      -для f(n)=Ω( nlogbа+ε), ε>0, причем аf(n/b)≤сf(n) для некоторой константы с
< 1 и достаточно больших n, верно, что Т(n)=Θ(f(n)).
      Суть теоремы – в сравнении функции f(n) с nlogbа , если одна из функций
растет быстрее другой, то она и определяет порядок роста Т(n). Если функции
одного порядка, появляется логарифмический множитель.

       3.6 NР – полнота

       Если время работы алгоритма на входе длины n составляет О(nк) при не-
котором к, не зависящем от n, то алгоритм называется полиномиальным. Задача
называется полиномиально разрешимой, если для нее существует полиномиа-
льный алгоритм. Для некоторых задач алгоритмы не полиномиальны. Есть так-
же неразрешимые задачи. Классическая задача – выяснить, останавливается ли
данная программа на данном входе, - не может быть решена никаким алгорит-
мом. Специалисты считают полиномиальные алгоритмы практически приемле-
мыми, а алгоритмы, требующие времени, «большего», чем полиномиальное, -
представляющими лишь теоретический интерес. К характеристике полиномиа-
льных алгоритмов следует добавить их замкнутость: композиция (последовате-
льное выполнение) полиномиальных алгоритмов есть полиномиальный алго-
ритм. Достаточно полное изложение вопросов сложности алгоритмов имеется в
/5/. Здесь приводятся лишь некоторые сведения.

                      3.6.1 Задачи разрешения. Класс P

      Рассмотрим абстрактную задачу – бинарное отношение β между элемен-
тами множества условий U и множества решений V. Например, в задаче обхода
графа условиями являются матрицы смежностей, а решениями – последовате-
льности вершин. Задачами разрешения называются задачи, в которых требуется
ответить («да» или «нет») на поставленный вопрос, то есть построить функцию
f с областью определения U и множеством значений V= 0,1. Если предпола-
гать, что входные данные для алгоритма представлены последовательностью
битов (или последовательностью символов другого алфавита мощности ≥2), то
абстрактная задача переходит в так называемую строковую задачу. Строковая
задача называется полиномиальной, если существует алгоритм, который решает
ее при длине входа n за время О (nк) для некоторого к.
      Множество полиномиальных строковых задач разрешения называется
сложностным классом Р. Функция f: 0,1*→0, 1 называется вычислимой за
полиномиальное время, если существует полиномиальный алгоритм, перево-