Возможны различные подходы к оценке качества алгоритма, например, оценивается число команд (инструкции), из которых он состоит, число операций, объем используемой памяти. Будем считать, что алгоритм отождествляется с программой, работающей на идеальной ЭВМ, состоящей из процессора, памяти, входной и выходной лент. Ленты и память состоят из ячеек, каждая из которых может хранить двоичную запись одного числа.
Имеется два подхода к оценке времени и памяти, необходимых для выполнения программы: при равномерном весовом критерии считается, что каждая команда программы затрагивает один такт времени, и каждое число занимает одну ячейку памяти. Логарифмический весовой критерий учитывает ограниченность размера реальной ячейки памяти и основывается на предложении, что объем памяти для хранения числа n равен длине его двоичного представления l(n) = [log2n] + 1, а время исполнения команды пропорционально длине его операндов.
Временная сложность программы – это функция fmax(n), равная наибольшей из сумм времен, затраченных на каждую выполненную команду при обработке входных данных, состоящих из n чисел. Таким образом, для каждой n-ки (x1,…,xn)ÎD из области допустимых значений начальных данных (например, области определения частично рекурсивной функции) надо вычислить время t(x1,…,xn), затраченное на выполнение программы. Тогда временная сложность будет равна max{t(x1,…,xn):(x1,…,xn)ÎD}. Временная сложность в среднем при равномерном критерии равна: 
, где ôDô – число элементов области DÍNn, а x = (x1,…,xn) – элементы из D. Временная сложность в лучшем случае равна: fmin(n) = min{t(x):xÎD}. Такие же понятия определяются для объема памяти. Вместо времени t(x1,…,xn) рассматривается количество u(x1,…,xn) ячеек памяти, к которым обращалась программа, имеющая на выходе x1,…,xn.
Для описания асимптотического поведения сложностных функций используется следующий формализм: Говорят, что функция f(n) не больше по порядку, чем g(n), и пишут: f(n) = O(g(n)), если существует такая константа C > 0, что почти для всех n (т.е. для всех, кроме конечного множества значений n) справедливо f(n) £ Cg(n). Функции одного и того же порядка, если f(n) = O(g(n)) и g(n) = O(f(n)).
Труднорешаемые и NP-полные задачи
Алгоритм называется полиномиальным (или имеющим полиномиальную временную сложность), если его временная сложность f(n) равна: O(p(n)) для некоторого полинома p(n). Задача называется труднорешаемой, если для ее решения не существует полиномиального алгоритма.
Попытки найти алгоритмы полиномиальной сложности для решения некоторых задач привели к понятию недетерминированной машины Тьюринга для (НДМТ) распознавания свойств, полученной из обычной машины Тьюринга заменой конечного состояния q0 на два заключительных состояния – qY и qN . Машина проверяет, удовлетворяют ли входные данные заданному свойству. Если она заканчивает работу в состоянии qY , то получен ответ «да», если заканчивает в состоянии qN , то получен ответ «нет». Недетерминированная машина Тьюринга, помимо головки чтения/записи имеет дополнительное устройство, которое называется угадывающем модулем. Этот модуль может только записывать на ленту. Угадывающий модуль дает информацию для записи «догадки».
Программа для НДМТ (НДМТ-программа) определяется как и для машины Тьюринга в виде частичной функции p: Q x A ® Q x A x {L,S,R}. Вычисление на НДМТ в отличии от вычисления на машине Тьюринга имеет две различные стадии.
На первой стадии происходит «угадывание». В начальный момент времени входное слово w записывается в ячейках с номерами 1, 2, …, |w|, головка чтения/записи смотрит на ячейку 0, пишущая головка угадывающего модуля смотрит на ячейку с номером –1. Угадывающий модуль начинает управлять угадывающей головкой, которая делает один шаг в каждый момент времени и либо пишет в находящейся под ней ячейке одну из букв алфавита A и сдвигается влево, либо останавливается. В последнем случае угадывающий модуль заканчивает работу и начинает работать программа p.
Начиная с этого момента, вычисление НДМТ-программы осуществляется по тем же правилам, что и вычисление на машине Тьюринга. Вычисление заканчивается тогда, когда управляющее устройство перейдет в одно из заключительных состояний (qY и qN); оно называется принимающим вычислением, если остановка происходит в состоянии qY . Остальные вычисления, в том числе не заканчивающиеся, называются непринимающими.
Любая НДМТ-программа p может иметь бесконечное число возможных вычислений при данном входе w, по одному для каждого слова-догадки из A*. Будем говорить, что НДМТ-программа p принимает w, если по крайней мере одно из ее вычислений, имеющих w на входе, является принимающим. Язык, распознаваемый программой p, — это язык Lp = {w Î A* : p принимает w}. Временем, требующимся НДМТ-программе p для того, чтобы принять слово w Î Lp , называется минимальное число шагов, выполняемых на стадии угадывания и проверки до момента достижения заключительного состояния qY , где минимум берется по всем принимающим вычислениям программы p на входе w. Временной сложностью НДМТ-программы p называется функция Tp : N+® N+, где N+ = {1, 2, 3, …}, определенная как Tp (n) = max {{1}È{m: существует w Î Lp , |w| = n, такое что время принятия w программой p равно m}}.
Если существует такой полином p(n) , что Tp (n) £ p(n) для всех n ³ 1, то НДМТ-программа называется имеющей полиномиальное время работы.
Класс NP – это класс (не обязательно всех) задач распознавания свойств (т.е. задач, решениями которых могут быть либо «да», либо «нет»), которые могут быть решены с помощью НДМТ-программы с полиномиальным временем работы. Большинство практически важных задач, для которых в настоящее время не известны полиномиальные алгоритмы, после переформулировки их в виде задач распознавания свойств, попадают в этот класс.
Задача из NP называется NP-полной, если всякая другая задача из класса NP может быть сведена к ней за полиномиальное время. Таким образом, если для некоторой NP-полной задачи существует полиномиальный алгоритм, то и любая задача из класса NP полиномиальна разрешима, а если какая-то задача из NP труднорешаемая, то и любая NP-полная задача является труднорешаемой.