Важным мотивом, побуждающим рассматривать формальные модели вычислений, является желание раскрыть вычислительную сложность различных задач с целью получить нижние оценки на время вычисления. Чтобы показать, что не существует алгоритма, выполняющего данное задание менее чем за определённое время, необходимо точное и подчас высокоспециализированное определение того, что есть алгоритм. Одним из примеров такого определения служат машины Тьюринга.
Машина Тьюринга – простейшая модель вычислений; существуют и более сложные модели, например многоленточные машины Тьюринга, автоматы Неймана [7]. Все они могут быть использованы для решения тех задач, для которых существует алгоритм. На основе этих моделей строятся более специализированные модели вычислений, а именно: неветвящиеся арифметические программы, битовые вычисления, вычисления с двоичными векторами и деревья решений.
Алгоритмы имеют следующие характеристики:
1) сложность;
2) трудоёмкость;
3) надежность и др.
Далее рассматривается только первая характеристика – сложность. Для оценки сложности алгоритмов существует много критериев. Чаще всего важен порядок роста необходимых для решения задачи времени и ёмкости памяти (количество ячеек для хранения данных) при увеличении количества входных данных. Свяжем с каждой конкретной задачей некоторое число, называемое её размером, которое выражало бы меру количества входных данных. Например, размером задачи умножения матриц может быть наибольший размер матриц сомножителей; размером задачи о графах может быть число рёбер данного графа и т.п.
Время, затрачиваемое алгоритмом, как функция размера задачи, называется временной сложностью этого алгоритма. Поведение этой сложности в пределе при увеличении размера задачи называется асимптотической временной сложностью. Аналогично определяются ёмкостная сложность и асимптотическая ёмкостная сложность.
Именно асимптотическая сложность алгоритма определяет в итоге размер задач, которые можно решить этим алгоритмом. Если алгоритм об-рабатывает входы размера n за время C n2, где C - некоторая постоянная, то говорят, что временная сложность этого алгоритма есть O(n2) (читается “порядка n 2“). Точнее, говорят, что неотрицательная функция g (n)есть O (f (n)), если существует такая постоянная C, что g (n)£C f (n) для всех, кроме конечного (возможно, пустого) множества, неотрицательных значений n.
Временная сложность в худшем случае (или просто временная сложность) алгоритма - это функция f(n), равная наибольшей (по всем входам размера n) из сумм времён, затраченных на каждый выполненный оператор. Временная сложность в среднем - это среднее, взятое по всем входам размера n, тех же самых сумм.
Аналогично определяется понятие для ёмкости памяти, только вместо "времён, затраченных на каждый выполненный оператор", следует подставить "ёмкость всех ячеек, к которым было обращение".
Определение. Говорят, что неотрицательные функции f1(n) и f2(n) полиномиально связаны (эквивалентны), если найдутся такие полиномы P1(x)и P2(x), что для всех n справедливы неравенства f1 (n)£P1(f2 (n)) и f2 (n)£P2(f1 (n)).
Пример 4.1. Пусть f1(n)=2n2 и f2=n5. Покажем, что функции f1 и f2 полиномиально связаны, для чего введём в рассмотрение полиномы P1(x) =2x иP2(x)= x3. Имеем 2 n 2£2(n 5)и n 5£(2 n 2)3 = 8 n 6.
Пример 4.2. Для функций f1(n)=n 2и f2(n)= 2 n не удаётся подобрать такие полиномы P1(x) и P2(x), чтобы выполнились неравенства f1 (n)£P1(f2 (n))и f2 (n)£P2(f1 (n)) при любом n, так как показательная функция с ростом n растёт быстрее степенной.
Не важно, как алгоритм представлен - в терминах языка высокого уровня или последовательностью двоичных символов; если алгоритм имеет полиномиальную (экспоненциальную) сложность для первого представления, то он будет иметь также полиномиальную (экспоненциальную) сложность и для второго представления.
Говорят, что данный алгоритм является алгоритмом с полиномиальным временем, если время его работы, т.е. число элементарных двоичных операций, которые он выполняет на входной строке длины l, ограничено сверху некоторым полиномом P (l). Класс всех задач, решаемых такими алгоритмами, обозначается через P; в этот класс очевидно не входят задачи, для решения которых необходим экспоненциальный алгоритм.
Введём в рассмотрение класс NP задач, которые можно решить за полиномиальное время с помощью недетерминированного алгоритма. В отличие от детерминированного алгоритма, в котором для любого данного состояния[1] существует не более одного вполне определённого следующего состояния, в недетерминированном алгоритме может быть больше одного допустимого следующего состояния[2]. Отметим, что P ÍNP.
Задача A является NP–трудной, если детерминированный полиномиальный алгоритм её решения можно использовать для получения детерминированного полиномиального алгоритма для каждой задачииз NP. Другими словами, задача A является NP–трудной, если она по крайней ме-ре так же трудна, как и любая задача в NP. NP–трудная задача из NP на-зывается NP–полной; такая задача не труднее, чем любая задача из NP.