Доказательство. Корректность алгоритма следует из леммы 2.
Номер компонента каждого узла (вершины) хранится в некоторой таблице. Выбор ребра наименьшего веса среди оставшихся занимает время O(e), а поиск компонент, в которых находятся вершины этого ребра – O(m). Если вершины принадлежат разным компонентам, на просмотр таблицы для объединения всех узлов с соответствующими номерами нужно время – O(m). Таким образом, общее время работы алгоритма – O(e(e+m)). Это время полиномиально зависит от “размера” входных данных, т. е. m +e.
Для реализации решения проблемы ОДМB на машине Тьюринга потребуются уточнения как постановки задачи, так и времени решения.
- Проблема поиска ОДМВ для реализации на машине Тьюринга может быть сформулирована так: “Для связного графа G и предельного числа W выяснить, имеет ли G остовное дерево с весом не более W?”
- Поскольку входом машины Тьюринга является слово в некотором конечном алфавите, поэтому объекты входа алгоритма Крускала должны быть закодированы. Так что полученная цепочка превысит предполагаемый “размер” входа на логарифмический сомножитель от размера входных данных. Таким образом, все, что делается за полиномиальное время с использованием одной меры, можно сделать за полиномиальное время, используя другую меру.
Пример. Рассмотрим кодирование входа проблемы ОДМВ в алфавите, содержащем символы: 1,0, (,) , “,” .
Вершины графа обозначим числами 1,…,m. В начало кода поместим значения m и предельного веса W в двоичной системе счисления, разделенные запятой. Для ребра (i, j) веса w код записывается в виде ( i, j, w), где числа заданы в двоичной системе.Для графа, изображенного на рис. 10.1 с W=40, код имеет вид:
100,101000(1,10,1111)(1,11,1010)(10,11,1100)(10,100,10100)(11,100,10010).
Далее описанная версия алгоритма будет реализована на многоленточ - ной машине Тьюринга за O(n2) шагов, где n = m+e:
На первой ленте которой будем хранить информацию об узлах и те-кущих номерах компонентов, их содержащих.
Вторая лента используется для хранения информации о ребре наи-меньшего в данный момент веса среди ребер, не помеченных как “использованные”. Поиск непомеченного ребра наименьшего веса требует времени 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.
NP – полнота и сводимость
Наиболее убедительным аргументом в пользу того, что классы P и NP различны, является существование NP - полных задач. Это самые труднорешаемые задачи в классе NP. Для их решения используются недетерминированные машины Тьюринга с полиномиальным временем работы на ветвях, где они допускают данный вход. Недетерминирован - ная машина имеет возможность угадывать экспоненциальное число решений проблемы и параллельно проверять каждое из них (за полиномиальное время).
Понятие полиномиальной сводимости позволяет придать точный смысл тому, что одна проблема не менее сложна, чем другая.
Язык L ⊆ {0,1}* называется NP – полным, если 1) L ∈ NP и
для любого L’ ∈ NP : L’ ≤ P L.Теорема. Если некоторая NP – полная задача разрешима за полиномиальное время, то P = NP. Если в классе NP существует задача, не разрешимая за полиномиальное время, то все NP – полные задачи не разрешимы за полиномиальное время.
Доказательство. Пусть L - NP – полный язык разрешимый за полиномиальное время. По свойству 2, для любого языка L’ ∈ NP : L’ ≤ P L.
Тогда по лемме, L’ ∈ P, так что P = NP.
Если некоторый язык L’ ∈ NP не разрешим за полиномиальное время, и так как любой язык из класса NP полиномиально сводим к NP – полному языку L, то L не разрешим за полиномиальное время. Иначе по первой части теоремы, L’ разрешим за полиномиальное время, что противоречит условию.
Таким образом, гипотеза P ≠ NP означает, что NP – полные задачи не могут быть решены за полиномиальное время на детерминированной машине Тьюринга.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
