Алгоритмы и анализ сложности (стр. 7 )

2. Если будет найден ДА для решения хотя бы одной задачи, то это автоматически дает ДА для решения всех задач из (т. е. ).

3. Если в хотя бы одна задача, не имеющая ДА сложности , то и все задачи – такие же.

Также не доказано, что мн-во : существуют задачи, решаемые алгоритмами, к к-рым не удается свести задачи и для к-рых не найдены алгоритмы.

Рассмотрим еще 2 типа задач:

1. Задачи-дополнения задач (например, для -раскраски: «не вариантов раскраски графа в цветов»).

Если основная задача , то решением допол-ной будет просто отрицание результата основной.

Но если основная задача , то она и ее дополнение не симметричны из-за особенностей НА.

2. Задачи типа в оптимизационной постановке (минимальная раскраска, оптимальный маршрут коммив-ра) – для них необходимо сравнение различных решений.

Про задачи данных типов можно сказать:

1. К ним может быть сведена любая задача из (т. е. они не менее трудны, чем любая задача из ).

2. Для их решения не существует алгоритма.

3. Если бы родственные им задачи решались в , то и они сами решались бы в .

Такие задачи называются трудными (т. о., задачи – это трудные, для к-рых существует алгоритм).

Для многих задач показана их полнота или трудность    пока не доказано противное, нет смысла искать для их общего решения алгоритмы (в частных случаях это м\б возможным).

Для решения трудных задач можно использовать 2 пути:

1. Эффективное отсечение непригодных вариантов и\или поиск квазиоптимальных решений.

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

Связь задач по сложности

Представим работу НА в виде дерева:

По каждой из ветвей трудоемкость , а емкостная сложность .

Если моделировать НА с помощью ДА, то нужно использовать бэктрекинг и последовательный просмотр всех ветвей.

Если количество ветвлений на каждом шаге , то количество конечных вершин (листьев) и трудоемкость ДА в наихудшем .

Емкостная сложность ДА: .

Если – полином, то НА .

Если и, следовательно, – полиномы, то

НА , а ДА .

Покажем, что выполняется и более сильное условие:

если некоторый алгоритм , то его работу можно смоделировать с помощью ДА .

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

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

Затраты памяти для любого МО . Всего различных МО может быть , где – входной алфавит, а общий объем памяти при моделировании .

Обозначим : из МО можно перейти в МО за 1 шаг.

Приведем детерминированную рекурсивную функцию проверки, можно ли перейти из в за шагов.

проверка(c1, c2, k) {

       if (k == 1) {

               if (c1 == c2 || c1c2) выход(“да”);

               else выход(“нет”);

       }

       else {

               while (есть_непроверенное_МО(c3))

                       if (проверка(c1, c3, k/2) &&

                                проверка(c3, c2, (k+1)/2))

                               выход(“да”);

               выход(“нет”);

       }

}

Глубина рекурсии , для любого МО нужно общая емкостная сложность .

Мы смоделировали произвольный алгоритм (МТ) с с помощью детерминир-го (ДМТ), затратив памяти.

Следовательно, эти МТ и ДМТ полиномиально связаны по затратам памяти, т. е. .

Очевидно, что трудоемкость функции проверка() будет экспоненциальной.

Диаграмма классов задач

Доказательство -полноты

Для задачи выполняются 2 условия: