Машина Тьюринга M имеет временную сложность T(n),если на входе w длины n машина M делает не более T(n) переходов и останавливается независимо от того, допущен вход или нет. Язык L принадлежит классу P, когда для некоторой машины M с временной сложностью T(n) = p (n), где p (n) - полином, L = L(M). Напомним, что в данной ситуации нет разницы между языками, допускаемыми и распознаваемыми за полиномиальное время.
Пример P – проблемы: алгоритм Крускала.
Проблема построения остовного дерева минимального веса связного неориентированного графа решается при помощи алгоритмов Крускала и Прима. Каждый из них реализуется за полиномиальное время. Оба алгоритма используют принцип “жадной” стратегии, выбирая на каждом шаге “локально наилучший” вариант. На вход вычисляющей машины подается граф, представляемый своими вершинами и ребрами. Каждому ребру приписан целочисленный вес. Остовное дерево – это связный подграф, не имеющий циклов, содержащий все вершины графа. Остовное дерево минимального веса (ОДМВ) - это дерево наименьшего веса среди остовных деревьев графа.
Построение алгоритма Крускала:
Базис. Вначале каждая вершина есть компонента связности.
Индукционный шаг. Среди еще не выбранных ребер рассматриваем ребро минимального веса. Если связываемые этим ребром вершины принадлежат разным компонентам связности, то
a) ребро добавляется в остовное дерево;
b) связанные этим ребром компоненты связности объединяются.
В противном случае ребро отбрасывается. Выбор заканчивается, если выбраны все ребра, или когда число ребер остовного дерева не станет равным êV ê- 1.
Лемма 1. Пусть G = (V, E) - связный неориентированный граф; S = (V,T) - его остовное дерево. Тогда a) " v1, v2 Î V $! v1 a v2 (путь в S).
c) Если к дереву S добавить ребро (v1,v2)Î E \ T, то возникнет точно один цикл.
Доказательство. a) В противном случае S содержит цикл, что невозможно. b) В противном случае в S уже был цикл, что невозможно.
Лемма 2. Пусть G = (V,E) - связный неориентированный граф, ребрам которого приписаны целочисленный вес f :E ® N.
Если {(V1, T1), … , (Vk , Tk)}- лес, где V = È Vi , T = È Ti (k > 1);
i=1..k i=1..k
e = (v, w) Î E \ T – ребро наименьшего веса в E \ T, где v Î V1, w Ï V1.
Тогда найдется остовное дерево, содержащее TÈ{e}, веса, меньшего веса любого остовного дерева, содержащего T.
Доказательство. Допустим, что S’= (V, T’ ) – остовное дерево графа G, содержащее T и не содержащее e, наименьшего веса среди остовных деревьев, содержащих TÈ{e}. По лемме 1 добавление к S’ребра e образует цикл. Этот цикл будет содержать ребро e’= (v’, w’ ) ¹ e, где
v’Î V1, w’ Ï V1. По условие f (e) £ f (e’).
Рассмотрим подграф S, образованный удалением e’из S’и добавлением в S’ребра e. В S нет циклов, поскольку единственный цикл S’ был разорван удалением ребра e’. Граф Sсвязный, так как вершины v’ и w ’ остались соединенными другим путем цикла в S’. Таким образом, S - остовное дерево, содержащее T и e, и f(S) £ f(S’ ), что противоречит допущению минимальности дерева S’. “
Теорема.Алгоритм Крускала строит ОДНB для связного графа G=(V,E).
Время работы алгоритма не более O(e (e+m)).
Доказательство. Корректность алгоритма следует из леммы 2.
Номер компонента каждого узла (вершины) хранится в некоторой таблице. Выбор ребра наименьшего веса среди оставшихся занимает время O(e), а поиск компонент, в которых находятся вершины этого ребра – O(m). Если вершины принадлежат разным компонентам, на просмотр таблицы для объединения всех узлов с соответствующими номерами нужно время – O(m). Таким образом, общее время работы алгоритма – O(e(e+m)). Это время полиномиально зависит от “размера” входных данных, т.е. m +e. “
Для реализации решения проблемы ОДМB на машине Тьюринга потребуются уточнения как постановки задачи, так и времени решения.
- Проблема поиска ОДМВ для реализации на машине Тьюринга может быть сформулирована так: “Для связного графа G и предельного числа W выяснить, имеет ли G остовное дерево с весом не более W ?”
- Поскольку входом машины Тьюринга является слово в некотором конечном алфавите, поэтому объекты входа алгоритма Крускала должны быть закодированы. Так что полученная цепочка превысит предполагаемый “размер” входа на логарифмический сомножитель от размера входных данных. Таким образом, все, что делается за полиномиальное время с использованием одной меры, можно сделать за полиномиальное время, используя другую меру.
Пример. Рассмотрим кодирование входа проблемы ОДМВ в алфавите, содержащем символы: 1,0, (,) , “,” .
1. Вершины графа обозначим числами 1,…,m.
2. В начало кода поместим значения m и предельного веса W в двоичной системе счисления, разделенные запятой.
3. Для ребра (i,j) веса w код записывается в виде ( i, j, w), где числа заданы в двоичной системе.
Для графа, изображенного на рис. 10.1 с W=40, код имеет вид:
Далее описанная версия алгоритма будет реализована на многоленточ- ной машине Тьюринга за O(n2) шагов, где n = m+e:
1. На первой ленте которой будем хранить информацию об узлах и те-
кущих номерах компонентов, их содержащих.
2. Вторая лента используется для хранения информации о ребре наи-
меньшего в данный момент веса среди ребер, не помеченных как “использованные”. Поиск непомеченного ребра наименьшего веса требует времени O(n), поскольку каждое ребро просматривается только один раз, и сравнить вес можно, просматривая код входной цепочки.
3. Если ребро на некотором этапе выбрано, то соответствующие вершины помещаются на третью ленту. Чтобы установить компоненты этих двух узлов, надо просмотреть таблицу узлов и компонентов. Это потребует O(n) времени.
4. Четвертая лента может хранить информацию об объединяемых компонентах i и j. В этом случае просматривается таблица узлов и компонентов, и для каждого узла из компонента i номер компонента меняется на j. Эта процедура требует O(n) времени.
Таким образом, каждый этап работы алгоритма на многоленточной машине Тьюринга выполняется за время O(n). Число этапов e не превышает n, то время полной работы алгоритма равно O(n2). Для одноленточной машины Тьюринга на это потребуется O(n4) шагов.
Реализация проблемы ОДМВ (“имеет ли граф G ОДМВ с весом, не более W ?”) принадлежит классу P. “
Полиномиальная сводимость в классе P
Дадим определение полиномиальной сводимости в терминах языков. Язык L1 сводится за полиномиальное время к языку L2 : L1 £ P L 2 ,
если существует функция f: {0,1}* ® {0,1}* , вычислимая за полиномиальное время, такая, что для любого x Î {0,1}*, x Î L1 « f(x) Î L2.
Лемма. Если язык L1 Í {0,1}* сводится за полиномиальное время к языку L2 Í {0,1}* и L2 ÎP, то L1 ÎP.
Доказательство. Пусть M2 - машина, распознающая язык L2 за полиномиальное время, F – сводящая машина, вычисляющая на входе x за полиномиальное время значение функции f(x). Построим машину M1 , разрешающую за полиномиальное время язык L1. Ответить на вопрос о принадлежности x языку L1 можно, ответив на вопрос о принадлежности f(x) языку L2 . Т.е. машина M1 получается композицией машин F и M2.
Очевидно, что время работы машины M1 есть O(nk+ (cn k) j ) , где n – длина входа x. “
