Сложность вычислений - Методичка

МЕТОДИЧЕСКИЕ УКАЗАНИЯ К КУРСУВ математической логике определяются разрешимые и неразрешимые проблемы, а также методы их сводимости друг к другу. В вычислительной практике более существенна как раз эта сторона алгоритмических проблем - их внутренняя сложность и сложность реализующих их вычислительных моделей. Первый базируется на поиске оценок сложности, не зависящих от выбора вычислительной модели, т.е. на внутренней сложности алгоритма. На втором пути исследуются параметры вычислительных моделей, например, число лент многоленточных машин Тьюринга или мощности их языков. Третий путь аксиоматический, здесь Блюмом были предложены две аксиомы меры сложности.Язык L допускается (распознается) за полиномиальное время, если существует машина M, которая допускает (распознает) язык L, причем всякое слово WI L допускается (распознается) за время O(nk), где n - длина слова w, а k - не зависящее от w число. В одну сторону тривиально, если машина M распознает язык L, то она и допускает язык L. Обратно, пусть язык L допускается машиной M за время O(nk), т.е. существует константа c, что любое слово из L длины n допускается не более, чем за T = c?nk шагов. В начальной конфигурации многоленточной машины на первой ленте размещается вход (конечная последовательность символов, куда не входит L), все клетки остальных лент содержат символ L, считывающие головки всех лент находятся в начальном состоянии. Если sw кратчайшая последовательность возможных шагов работы машины, которая оканчивается допускающей конфигурацией, то ?sw? есть время, затраченное машиной на обработку входа w.§3. Язык диагонализации LdУниверсальный язык LuДопускающие язык L машины M останавливаются на словах (цепочках) WIL=L(M), а на словах WIL могут также останавливаться, не допуская, такие языки L будем называть рекурсивными (разрешимыми), или - работать бесконечно, назовем такие языки нерекурсивными (неразрешимыми). Иначе машина Mi , или i-ая машина, Тьюринга имеет своим кодом цепочку wi , и номер i. Очевидно, что не все двоичные цепочки wi являются правильными кодами машин Тьюринга, в этом случае будем считать, что машина Mi имеет одно состояние и у нее нет переходов, т.е. такая машина Mi останавливается сразу на любом входе. Теперь можно представить таблицу, у которой по горизонтали стоят номера всех цепочек, а по вертикали номера всех машин Тьюринга (все натуральные числа), а на пересечении i-й строки и j-го столбца стоит 1, если машина Mi допускает цепочку wj , и 0 - если не допускает. Допустим противное, что существует машина Mi , допускающая язык Ld , так что Ld = L(Mi).2.1 Алгоритм КрускалаМашина Тьюринга M имеет временную сложность T(n), если на входе w длины n машина M делает не более T(n) переходов и останавливается независимо от того, допущен вход или нет. Тогда найдется остовное дерево, содержащее TE{e}, веса, меньшего веса любого остовного дерева, содержащего T. Допустим, что S’ = (V, T’ ) - остовное дерево графа G, содержащее T и не содержащее e, наименьшего веса среди остовных деревьев, содержащих TE{e}. Выбор ребра наименьшего веса среди оставшихся занимает время O(e), а поиск компонент, в которых находятся вершины этого ребра - O(m). Пусть M2 - машина, распознающая язык L2 за полиномиальное время, F - сводящая машина, вычисляющая на входе x за полиномиальное время значение функции f(x).Языки класса ZPP (безошибочные, вероятностные полиномиальные) также используют случайные числа, но алгоритм дает ответ: “да”, если вход принадлежит языку, и “нет” - в противном случае . Измененная машина Тьюринга допускает язык L’ и время ее работы совпадает с T(M) 1. Т.е. Применим к x I L‘ сводящий алгоритм L’ <p R’ , а результат на выходе подадим недетерминированной машине Тьюринга, вычисляющей проблему R’, построенную композицию объявим машиной, вычисляющей язык L’, откуда L’ I NP, следовательно, L I NP. Если t - число ленточных символов, а s - число состояний машины M, то число различных МО машины, использующей p(n) клеток, не более s ? p(n) ? t p(n) , т.е. можно выбрать одно из s состояний, поместить считывающую головку в одну из p(n) позиций и заполнить p(n) клеток любой из t p(n) последовательностей ленточных символов. Получив вход w, машина D исследует тройки вида [I0, J, m ], где I0 - исходное МО, J - заключительное МО машины N, в котором используется не более p(n) клеток. m в каждом вызове рекурсивной процедуры уменьшается в два раза, пока не станет равным 1.Двоичное представление p занимает n битов, т.е. само p близко к 2 n, так что любое вычисление, включающее p шагов не полиномиально по времени, занимает время не менее O(2 n). Метод генерации n-битовых простых чисел состоит в следующем: случайно выбирается n-битовое число и много раз применяется алгоритм Монте-Карло для распознавания составных чисел. Если некоторая проверка показала, что число составное, то число точно не простое. Т.е. с большой долей уверенности можно сказать, что число простое, и этим обосновать безопасность криптографических операций.