Введение в теорию np-полных задач Задачи, алгоритмы и сложность

Под массовой задачей мы будем понимать некоторый общий вопрос, на который следует дать ответ. Обычно задача содержит несколько параметров или несколько переменных значений, которые неопределены. Массовая задача П определяется информацией:

1. Общим списком всех её параметров.

2. Формулировкой некоторых свойств, которым должен удовлетворять ответ.

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

Рассмотрим массовую задачу О КОММИВОЯЖЁРЕ. Параметрами в данной задаче являются конечный набор городов C = {c₁,c₂,…,c_n} и расстояние d(c_i,c_j) между парой городов c_i,c_j. Решением является упорядоченный набор <C_k1,C_k2,…,C_kn> заданных городов, в котором каждый C_ki не совпадает ни с каким другим, и величина принимает минимальное значение. Индивидуальная задача о коммивояжёре задаётся следующим образом:

C={c₁, c₂, c₃, c₄}

d(c₁, c₂) = 10,

d(c₁, c₃) = 5,

d(c₁, c₄) = 9,

d(c₂, c₃) = 6,

d(c₂, c₄) = 9,

d(c₃,c₄) = 3

< C₁, C₂, C₄, C₃>

Под алгоритмом будем понимать общее выполнение, шаг за шагом, процедуры решения задачи. Для определённости, мы будем считать её программой для компьютерного написания на формальном машинном языке. Будем говорить, решая массовую задачу П, если П применимо к любой индивидуальной задаче I, то и решение П даёт решение задачи I.

Нам необходим наиболее “эффективный” алгоритм решения задачи. Под самым эффективным алгоритмом понимается самый быстрый алгоритм решения. Время работы алгоритма удобно выразить в виде функции одной переменной. Эта переменная характеризует “размер” индивидуальной задачи, т.е. объём входных данных, требуемых при её описании. В дальнейшем, сравнительную сложность задач будем описывать через их размеры. Описание индивидуальной задачи можно рассматривать как одну конечную цепочку, состоящую из символов конечного входного алфавита.

Предположим, что заранее выбран такой способ, что с каждой массовой задачей связана некоторая фиксированная система кодирования. Она отображает индивидуальность задачи в цепочки символов. Входная длина индивидуальной задачи I из П определяется как число символов в цепочке, полученной применением к задаче I схемы кодирования для массовой задачи П. Эта входная длина используется в качестве формальной характеристики размера индивидуальной задачи.

Временная сложность алгоритма отображается функцией затраты времени, требующегося для его работы.

Данная функция каждой входящей цепочки длины n ставит в соответствие максимальное по всем индивидуальным задачам длины n время, затрачиваемое алгоритмом на решение этой задачи. Эта функция не будет полностью определена, пока не зафиксирована схема кодирования и не выбрано вычислительное устройство, определяющее время работы.

Полиномиальные алгоритмы. Труднорешаемые задачи.

Для сравнения эффективности алгоритмов предлагается подход, основанный на различии полиномиальных и экспоненциальных алгоритмах. Будем говорить, что функция f(n) есть O(g(n)), если существует константа c такая, что |f(n)|≤c·|g(n)|, n≥0.

Полиномиальными алгоритмами называют алгоритмы, у которых временная сложность равна O(p(n)), где p(n) – некоторая полиномиальная функция, n – длина входной цепочки алгоритма.

Алгоритмы, временная сложность которых не поддаётся подобной оценке, называются экспоненциальными.

Временная Объём входной информации, обрабатываемый алгоритмом

cложность алгоритма вед. времени

N	N1	100N1	1000N1
N^2	N2	10N2	31.6N2
N^3	N3	4.64N3	10N3
N^4	N4	2.5N4	3.98N4
2^N	N5	N5+6.64	N5+9.97

Большинство экспоненциальных алгоритмов представляет собой варианты полного перебора.

Полиномиальный алгоритм можно построить лишь тогда, когда удаётся проникнуть в суть решения задачи. Обычно считается, что задача не является хорошо решаемой, если для неё не получен полиномиальный алгоритм. Подобного рода задачи будем считать труднорешаемыми.

Понятие труднорешаемой задачи оказывается по существу независимым от конкретной схемы кодирования и модели компьютера, используемых при определении временной сложности.

Рассмотрим схему кодирования.

Предположим, например, что условие решаемой задачи представлено графом G=(V,E), где

V – множество вершин,

E – множество рёбер.

Причём, каждое ребро понимается как неупорядоченная пара вершин, которые соединяются.

Условия данной задачи могут быть написаны разными способами.

Способ записи	Цепочка символов	Длина цепочки		V1		V2
Список вершин цепочки	V[1] V[2] V[3] V[4] (V[1] V[2]) (V[2] V[3])	36
Список соседей	(V[2]) (V[1] V[3]) (V[2]) ( )	24
Строки матрицы смежности	0100 / 1010 / 0100 / 0000	19
				V3		V4

Представленные схемы кодирования дают входы различной длины, однако можно проверить, что они отличаются друг от друга не более, чем полиномиальным образом. Это означает, что полиномиальный алгоритм, работающий с входными данными любой из кодировок, в любой другой кодировке будут также иметь полиномиальную сложность. Неформально определяя “разумную” схему кодирования, мы можем выдвинуть два требования к ней:

1. Код любой индивидуальной задачи I должен быть “сжатым”, т.е. не содержать избыточной информации или избыточных символов.

2. Числа, входящие в условие задачи I, должны быть представлены в двоичной системе счисления (или с любым другим основанием отличным от 1).

Если ограничимся рассмотрением только тех схем кодирования, которые удовлетворяют этим условиям, то выяснение вопроса о том, является ли данная задача трудно решаемой, не будет зависеть от выбора конкретной схемы кодирования. Все эти схемы будут полиномиально эквивалентны между собой. Аналогичное замечание можно сделать и относительно выбора модели вычислительного устройства. Все известные в настоящей момент времени модели эквивалентны относительно полиномиальновременной сложности. В следующей таблице представлено время, требуемое машиной А для моделирования работы алгоритма сложности T(n) на машине B.

Моделируемая машина B	Моделирующая машина A
	1МТ	kМТ	МПД
М.Т. с 1 лентой	-	O(T(n))	O(T(n)∙logT(n))
М.Т. с k – лентами	O(T2(n))	-	O(T(n)∙logT(n))
Машина произвольного доступа (МПД)	O(T3(n))	O(T2(n))	-

Можно ожидать, что и любая иная “разумная модель” вычислительного устройства будет полиномиально эквивалентна рассмотренной модели. Под словами «разумная модель» мы будем понимать то, что объём работы, выполняемый вычислительным устройством в единицу времени, ограничивается сверху полиномом.