Введение в теорию 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 – длина входа алгоритма.

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

Временная сложность	Современные ЭВМ	*100	*1000
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))	-

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