Понятие алгоритма очень долго оставалось интуитивным понятием. Только в 30-е годы XX века в работах выдающихся математиков Д.Гильберта, А.Черча, С.Клини, Э.Поста и А.Тьюринга были предложены формальные определения алгоритма на основе понятия рекурсивной функции и на основе описания алгоритмического процесса. Тем самым сформировалась теория алгоритмов - новое направление в математике, которое стало впоследствии теоретической основой развития  вычислительной техники. В настоящее время теория алгоритмов бурно развивается, многие ее понятия проясняются и уточняются (доказуемость, разрешимость,  эффективность и др.).

Очень важным понятием в математике (интуитивно ясным, но не очень просто  формализуемым) является сложность алгоритма. Приведем простой пример. Пусть  требуется угадать задуманное число, про которое известно, что оно натуральное и не превосходит 1000. Разрешается задавать вопросы, на которые можно ответить "да" или "нет". Одним из способов (алгоритмов) угадывания может быть такой: последовательно перебираются все числа от 1 до 1000 до тех пор, пока нужное  число не будет найдено. В худшем случае для этого потребуется 999 вопросов. Однако можно предложить и другой алгоритм, позволяющий угадать число за 10 вопросов: сначала выясняется, больше ли угаданное число 500 или нет, если да,  то больше 750 или нет и т.д. С каждым шагом число возможных кандидатов  уменьшается в два раза. Здесь сложностью алгоритма можно считать число вопросов. Тогда первый алгоритм в 100 раз "сложнее" второго. Если алгоритм проводит серии вычислений, сложностью алгоритма можно считать число совершаемых операций. При этом, если в алгоритме встречаются только умножение и сложение, под сложностью часто понимается только число умножений, поскольку эта операция требует существенно большего времени. На практике необходимо также учитывать стоимость операций, выполняемых алгоритмом, и т.п.

В математической теории сложности вычислений рассматриваются алгоритмы решения не конкретных задач, а так называемых  массовых задач. Массовую задачу удобно представлять себе в виде бесконечной серии индивидуальных задач. Индивидуальная задача характеризуется некоторым размером, т.е. объемом входных данных, требуемых для описания этой задачи. Если размер индивидуальной задачи - некоторое натуральное число n, тогда сложность алгоритма решения массовой задачи становится функцией от n.

 Рассмотрим алгоритм простого перебора всех двоичных ключей длины n. Ясно, что таких ключей - 2ⁿ, и поэтому в данном алгоритме 2ⁿ шагов, т.е. его  сложность равна 2ⁿ. Это простейший пример экспоненциального алгоритма (его сложность выражается через n экспонентой). Большинство экспоненциальных  алгоритмов - это просто варианты полного перебора.

Рассмотрим теперь алгоритм умножения столбиком двух n-значных чисел. Он  состоит из n² умножений однозначных чисел, т.е. его сложность, измеренная количеством таких умножений, равна n². Это - простейший пример  полиномиального алгоритма (его сложность выражается через n полиномом).  Достаточно очевидно, что для решения одной и той же математической задачи  могут быть предложены различные алгоритмы. Поэтому под сложностью задачи²⁰ понимают минимальную сложность алгоритмов ее решения. В математике есть много задач, для решения которых пока не удалось построить полиномиальный алгоритм. К ним относится, например, задача коммивояжера: есть n городов, соединенных сетью дорог, и для каждой дороги указана стоимость проезда по ней; требуется указать такой маршрут, проходящий через все города, чтобы стоимость проезда по этому маршруту была минимальной.

Основная практическая причина для анализа алгоритмов - необходимость получения оценок или границ для объема памяти или времени работы (и прочих ресурсов машины и пользователя), которые потребуются алгоритму для успешной обработки данных. Анализ полезен при проектировании программы чтобы исключить появление неработоспособных по памяти или времени систем, выявить узкие места в программе. Желательно иметь количественный критерий для сравнения разных алгоритмов решения одой задачи, механизм выявления более эффектиных алгоритмов и замены устаревшгих. Для исследования эффективности алгоритм А решения задачи Р рассматривается как способ определения последовательности операций, преобразующих исходные данные Р в требуемый  результат, программа - последовательность команд (операторов), выполняющих то же самое. Используемые в алгоритме структуры данных при этом проходят ряд промежуточных состояний. Количество этих состояний, или суммарная трудоемкость операций и команд  (затраченное машинное время) определяют f(A,Р) трудоемкость или временную сложность решения задачи Р алгоритмом А. Трудоемкость решения задачи Р алгоритмом А можно узнать, проведя вычислительный эксперимент, например, решив с помощью А эту задачу и подсчитав затраченное время или требуемое количество операций. Однако, алгоритм предназначен для решения большого класса задач а трудоемкость определяется для каждой задачи индивидуально. Поэтому множество решаемых алгоритмом задач разбивают на классы, трудоемкость алгоритма внутри которых сопоставима.

         Классы задач обычно определяются одним или несколькими целочислеными параметрами - размерностями, как правило, характеризующими используемые структуры данных. Обозначим размерность задачи n (n - обычно целое число, но может быть вектором и более сложной структурой), F(A, n) - верхнюю границу числа операций требуемых алгоритму А для решения любой задачи размерности n. Тогда

F (A, n) = MAX{f(A, P)/задача P имеет размерность n }

          Оценку временной сложности алгоритма можно не только найти экспериментально, но и расчитать теоретически для произвольного значения n. Поведение F(A, n)²¹ в пределе при увеличении размерности задачи называется асимптотической временной сложностью. Асимптотическая сложность алгоритма важна, поскольку определяет размерность задач, которые можно решить этим алгоритмом.

          Алгоритм A называется полиномиальным алгоритмом²², если F(A,n) растет не быстрее, чем полином от n, иначе алгоритм называется экспоненциальным алгоритмом.

За критерий оценки временной сложности алгоритма можно считать и среднее ожидаемое время решения  задач какого-либо класса.

          Полиномиальные алгоритмы предпочтительнее при решении задач большой размерности, если же размерность задачи не велика, то предпочтительнее (даже и по времени счета) более простые алгоритмы.

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

               h(U, P) = MIN{f(A, P)/алгоритм A содержится в классе U }  

так и класса задач, заданной размерности  n

                       H(U, n) = MIN{F(A, n)/алгоритм A содержится в классе U }

          Эталоном класса алгоритмов считаются алгоритмы, реализуемые конечным автоматом под названием машина Тьюринга. Про задачу (класс задач) говорят²³, что она имеет полиномиальную временную сложность, т.е. относится к классу Р - если существует алгоритм этой машины, асимпототически решающей данную задачу за полиномиальное время. В противном случае задача (класс задач) имеет сложность NP или экспоненциальную сложность.

          Если ограничиться оперативной памятью компьютера (отвлекаясь от внешней памяти, ввода и вывода), то его состояние определяется перечнем значений, записанных в его ячейках. Тогда логично работу программы интерпретировать как процесс перевода исходного (начального) состояния компьютера (данных задачи)  в конечное состояние (найденное решение задачи). 

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

Чтобы охарактеризовать сложность работы алгоритма (т. е. способа вычисления функции), мы должны принять во внимание работу алгоритма на всех входах. Сделаем мы это одним из наиболее распространенных способов, который называется "сложность в наихудшем случае".

Будем говорить, что машина Тьюринга M работает за время T_M(n), если максимальное (по всем входам длины n) количество тактов, которое проработает M до остановки, равно T_M(n),. Аналогично, машина Тьюринга  M работает на памяти S_M(n), если наиболее удаленное от начала ленты положение головки при вычислениях на входах длины n  равно S_M(n).

Решать задачу можно разными способами и есть  разные формальные модели вычислений. К тому же, наивно определять сложность задачи по сложности наилучшего алгоритма, ее решающего. Поэтому принят другой способ характеризации сложности задачи. Он состоит в том, что выделяются классы тех функций, вычисление которых возможно при задаваемых ограничениях на потребляемые ресурсы. Наиболее важные классы получаются, если накладывать ограничения на рост времени работы и/или используемой памяти в зависимости от длины входного слова. А наиболее важное различие между эффективными и неэффективными вычислениями  задается функциями полиномиального роста. Функция f(n) называется функцией полиномиального роста, если для некоторой константы  d при достаточно больших n выполняется неравенство f(n)n^d, что будем обозначать как f(n) =poly(n).

          Определение 1.   Функция  f принадлежит классу P (и называется полиномиально вычислимой), если она вычислима на машине Тьюринга M, для которой T_M(n)=poly(n).

Определение 2.   Функция f принадлежит классу P_S (и называется вычислимой с полиномиальной памятью), если она вычислима на машине Тьюринга M, для которой S_M(n)=poly(n).

Для огромного числа естественно возникающих вычислительных задач не удается ни построить эффективный (полиномиальный) алгоритм, ни доказать отсутствие такого алгоритма. Например, решение линейного уравнения в неотрицательных целых числах. В этой связи необходимо иметь теорию, в которой такие задачи можно доказуемо отделить от простых задач. Подходящая теория была построена в начале 70-х годов и получила с тех пор широкое распространение. Основная идея состоит в том, чтобы ввести на множестве задач отношение сводимости ("задача A не сложнее задачи B") и характеризовать сложные задачи как задачи, к которым сводятся все задачи из некоторого класса.

Определение 3  (сводимость по Карпу). Функция  f₁ сводится к функции f₂ (обозначение f₁f2), если существует такая fP  функция , что x f₁(x)=f₂(x).

Сводимость по Карпу также называют полиномиальной сводимостью, а часто - просто сводимостью. Отношение  будем рассматривать как формальный вариант отношения "задача f₁ не сложнее задачи f₂".

Рассмотрим основные характеристики класса NP. Дадим неформальное описание этого класса задач. У нас появляется новый персонаж - Советник. От Исполнителя Советник отличается двумя чертами: он интеллектуально всемогущ и пристрастен (это означает, что Советник хочет, чтобы у рассматриваемого объекта было признано наличие исследуемого свойства, безотносительно к истинному положению дел). Последняя особенность не позволяет Исполнителю слепо опираться на мнение Советника: оно всегда одинаково. Исполнитель может задавать Советнику вопросы и действовать, исходя из полученных ответов. Каждый вопрос-ответ считается одним  действием. Решение о значении функции принимает Исполнитель. Функция f(x) (характеристическая)  принадлежит классу NP, если существует алгоритм для пары (Исполнитель, Советник), который всегда (при любых возможных вариантах диалога между Исполнителем и Советником) заканчивается за полиномиальное от длины входа время и результат работы которого удовлетворяет следующему условию: если f(x)=1, то существует такой вариант диалога между Исполнителем и Советником, что результат равен 1; если же f(x)=0, то при любом варианте диалога  результат равен 0.

Из данного выше неформального определения ясно, что PNP (Исполнитель может ничего не спрашивать). Прежде чем давать формальное определение класса NP, заметим следующее. Исполнитель работает вполне определенным образом, а Советник - всеведущ. Поэтому, посмотрев на вход, Советник может сразу сообщить Исполнителю весь их диалог, а Исполнитель - убедиться, что Советник не соврал; Исполнителю на это потребуется время, полиномиально зависящее от длины диалога.

    Определение 4. Функция f(x) (со значениями в множестве {0, 1}) принадлежит классу NP, если она представима в форме

f(x)=y((<q())&R(x, y)

где q() - полином, R(x, y)P, а  , - длина слов x, y соответственно. 

Здесь (и всюду далее) мы отождествляем логические значения "ложь" и "истина" с 0 и 1 соответственно. Определение 4 нужно понимать так: y - это сообщение Советника Исполнителю, а R(x, y) - алгоритм проверки, который осуществляет Исполнитель.

Слово  в данном выше определении можно понимать как "подсказку" Исполнителю, воспользовавшись которой он может проверить выполнение NP-свойства. Другими словами, у NP-задачи есть ответ, который, быть может, трудно найти, но проверить правильность ответа - легко.

    Лемма 1 (без доказательства).   Пусть f₁f2. Тогда а) f₁Pf₂P; б)  f₂NPf₁NP.

Определение 5.   Функция fNP называется NP-полной, если любая функция из NP к ней сводится.

Если некоторую NP-полную функцию f можно вычислять за время T(n), то любую функцию g из NP можно вычислять за время T(n^s), где число s зависит от g, но не от входа.