Временная сложность алгоритма

В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе^[1]. Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, то есть при стремлении размера входа к бесконечности. Например, если существует число $n_{0}$ , такое, что время работы алгоритма для всех входов длины $n>n_{0}$ не превосходит $5n^{3}+3n$ , то временную сложность данного алгоритма можно асимптотически оценить как $O(n^{3})$ .

Временная сложность обычно оценивается путём подсчёта числа элементарных операций, осуществляемых алгоритмом. Время исполнения одной такой операции при этом берётся константой, то есть асимптотически оценивается как $O(1)$ . В таких обозначениях полное время исполнения и число элементарных операций, выполненных алгоритмом, отличаются максимум на постоянный множитель, который не учитывается в O-нотации. Так как время работы алгоритма может отличаться на входах одного и того же размера, обычно используется время работы в худшем случае, которое обозначается как $T(n)$ и определяется как наибольшее по всем входным данным длины $n$ время работы алгоритма. Реже, и это обычно оговаривается специально, вычисляется средняя сложность^[англ.], то есть математическое ожидание времени работы по всем возможным входам. Время работы алгоритма может быть классифицировано в зависимости от того, какая функция находится под О-нотацией. Например, алгоритм с $T(n)\in O(n)$ называют алгоритмом с линейным временем работы, а алгоритм с $T(n)\in O(n^{\alpha })$ для некоторого $\alpha >1$ называют полиномиальным.

Таблица сложностей по времени

Следующая таблица обобщает наиболее часто встречающиеся классы сложности. В таблице $poly(x)$ обозначает произвольный многочлен от $x$ , то есть $poly(x)=x^{O(1)}$ .

Название	Класс сложности	Время работы, $T(n)$	Примеры времени работы	Примеры алгоритмов
константное время		$O(1)$	$10$	Определение чётности целого числа (представленного в двоичном виде)
обратная функция Аккермана		$O(\alpha (n))$		Амортизационный анализ на одну операцию с использованием непересекающихся множеств
итерированно логарифмическое время		$O(\log ^{*}n)$		Распределённые раскраски циклов
дважды логарифмическое		$O(\log \log n)$		Время амортизации на одну операцию при использовании ограниченной очереди с приоритетами^[англ.]^[2]
логарифмическое время	DLOGTIME^[англ.]	$O(\log n)$	$\log n$ , $\log n^{2}$	Двоичный поиск
полилогарифмическое время		$poly(\log n)$	$(\log n)^{2}$
сублинейное время		$O(n^{c})$ при $0<c<1$	$n^{1/2}$ , $n^{2/3}$	Поиск в k-мерном дереве
линейное время		$O(n)$	$n$	Поиск наименьшего или наибольшего элемента в неотсортированном массиве
«n log-звёздочка n»		$O(n\log ^{*}n)$		Алгоритм триангуляции многоугольника Зайделя^[англ.].
линейно-логарифмическое время		$O(n\log n)$	$n\log n$ , $\log n!$	Самая быстрая сортировка сравнением^[англ.]
квадратичное время		$O(n^{2})$	$n^{2}$	Сортировка пузырьком, сортировка вставками, прямая свёртка
кубическое время		$O(n^{3})$	$n^{3}$	Обычное умножение двух $n\times n$ матриц. Вычисление частичной корреляции^[англ.].
полиномиальное время	P	$2^{O(\log n)}=poly(n)$	$n$ , $n\log n$ , $n^{10}$	Алгоритм Кармаркара для линейного программирования, АКС-тест простоты
квазиполиномиальное время	QP	$2^{poly(\log n)}$	$n^{\log \log n}$ , $n^{\log n}$	Самый быстрый известный $O(\log ^{2}n)$ — аппроксимационный алгоритм для ориентированной задачи Штейнера.
субэкспоненциальное время (первое определение)	SUBEXP	$O(2^{n^{\varepsilon }})$ для всех $\varepsilon >0$	$2^{\log n^{\log \log n}}$	Если принять теоретические гипотезы, BPP содержится в SUBEXP.^[3]
субэкспоненциальное время (второе определение)		$2^{o(n)}$	$2^{n^{1/3}}$	Самые быстрые известные алгоритмы разложения на множители целых чисел и проверки изоморфизма графов^[англ.]
экспоненциальное время (с линейной экспонентой)	E^[англ.]	$2^{O(n)}$	$1.1^{n}$ , $10^{n}$	Решение задачи коммивояжёра с помощью динамического программирования
экспоненциальное время	EXPTIME	$2^{poly(n)}$	$2^{n}$ , $2^{n^{2}}$	Решение задачи о порядке перемножения матриц с помощью полного перебора
факториальное время		$O(n!)$	$n!$	Решение задачи коммивояжёра полным перебором
дважды экспоненциальное время	2-EXPTIME^[англ.]	$2^{2^{poly(n)}}$	$2^{2^{n}}$	Проверка верности заданного утверждения в арифметике Пресбургера
Алгоритм Евклида		${\sqrt {\log _{}(\min(a,b))}}$
		${\sqrt[{n}]{\log _{n}(n)}}$	1 при n >= 1
Алгоритм Полига - Хеллмана		$O(\sum \limits _{i=1}^{s}\alpha _{i}(\log {p}+q_{i}))$		Если множители, на которые раскладывается $p-1$ , достаточно маленькие, то алгоритм очень эффективен
ρ-метод Полларда		${\textstyle p^{1/2}}$		Имеет эвристическую оценку сложности

Константное время

Говорят, что алгоритм является алгоритмом константного времени (записывается как время $O(1)$ ), если значение $T(n)$ ограничено значением, не зависящим от размера входа. Например, получение одного элемента в массиве занимает константное время, поскольку выполняется единственная команда для его обнаружения. Однако нахождение минимального значения в неотсортированном массиве не является операцией с константным временем, поскольку мы должны просмотреть каждый элемент массива. Таким образом, эта операция занимает линейное время, $O(n)$ . Если число элементов известно заранее и не меняется, о таком алгоритме можно говорить как об алгоритме константного времени.

Несмотря на название «константное время», время работы не обязательно должно быть независимым от размеров задачи, но верхняя граница времени работы должна. Например, задача «обменять значения $a$ и $b$ , если необходимо, чтобы в результате получили $a\leq b$ », считается задачей константного времени, хотя время работы алгоритма может зависеть от того, выполняется ли уже неравенство $a\leq b$ или нет. Однако существует некая константа $t$ , для которой время выполнения задачи всегда не превосходит $t$ .

Ниже приведен пример кода, работающего за постоянное время:

int index = 5;
int item = list[index];
if (условие верно) then
    выполнить некоторые операции с постоянным временем работы
else
    выполнить некоторые операции с постоянным временем работы
for i = 1 to 100
    for j = 1 to 200
        выполнить некоторые операции с постоянным временем работы

Если $T(n)$ равно $O(\alpha )$ , где $\alpha$ — константа, то это эквивалентно тому, что $T(n)$ равно $O(1)$ .

Логарифмическое время

Говорят, что алгоритм выполняется за логарифмическое время, если $T(n)=O(\log n)$ . Поскольку в компьютерах принята двоичная система счисления, в качестве основания логарифма используется $2$ (то есть $\log _{2}n$ ). Однако при замене основания логарифма $\log _{a}n$ и $\log _{b}n$ отличаются лишь на постоянный множитель $\log _{b}a$ , который в записи O-большое отбрасывается. Таким образом, $O(\log n)$ является стандартной записью для алгоритмов логарифмического времени независимо от основания логарифма.

Алгоритмы, работающие за логарифмическое время, обычно встречаются при операциях с двоичными деревьями или при использовании двоичного поиска.

$O(\log n)$ алгоритмы для работы с массивами данных размера $n$ считаются высокоэффективными, поскольку отношение времени выполнения одной операции к размеру массива уменьшается с увеличением этого размера.

Очень простой пример такого алгоритма — поиск слов в словаре. Рассмотрим словарь $D$ , в котором записаны $n$ слов, отсортированных по алфавиту. При этом считаем, что все слова имеют длину $O(1)$ и что мы можем за константное время получить доступ к любому элементу словаря по индексу. Пусть $D(k)$ — это $k$ -й элемент словаря, тогда можно проверить, лежит ли слово $\omega$ в словаре за $O(\log n)$ . Для этого нужно рассмотреть элемент словаря $D(\lfloor n/2\rfloor )$ , где $\lfloor ~\rfloor$ обозначает округление числа вниз. Если $D(\lfloor n/2\rfloor )<\omega$ , то нам стоит перейти в правую половину массива, иначе — в левую. В конце мы получим индекс первого слова, который равен или лексикографически больше, чем $\omega$ .

int find(vector<string> &D, string w) {
    int n = D.size();
    int l = -1, r = n;
    while(r - l > 1) {
        int m = (l + r) / 2;
        if(D[m] < w) {
            l = m;
        } else {
            r = m;
        }
    }
    return r;
}

Полилогарифмическое время

Говорят, что алгоритм работает за полилогарифмическое время, если $T(n)=O(\log ^{k}n)$ для некоторого $k$ . Например, задача о порядке перемножения матриц может быть решена за такое время на параллельной РАМ-машине^[англ.]^[4].

Сублинейное время

Говорят, что алгоритм выполняется за сублинейное время, если $T(n)=o(n)$ . В частности, сюда включаются алгоритмы, чья временная сложность соответствует указанным выше, а также, например, поиск Гровера со сложностью $O(n^{1/2})$ .

Обычно алгоритмы, которые, являясь точными, всё же работают за сублинейное время, используют распараллеливание процессов (как это делает алгоритм NC₁ вычисления определителя матрицы), неклассические вычисления (как в поиске Гровера) или имеют гарантированное предположение о структуре входа (как алгоритмы двоичного поиска и многие алгоритмы обработки деревьев). Однако такие формальные языки как язык слов, имеющих единичный бит в позиции, определяемой первыми $\log n$ битами слова, могут быть разрешимыми за сублинейное время даже несмотря на то, что любой бит может быть важен для определения принадлежности слова языку.

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

Так как такой алгоритм обязан давать ответ без полного чтения входных данных, он в очень сильной степени зависит от способов доступа, разрешённых во входном потоке. Обычно для потока, представляющего собой битовую строку $b_{1},\dots ,b_{k}$ , предполагается, что алгоритм может за время $O(1)$ запросить значение $b_{i}$ для любого $i$ .

Алгоритмы сублинейного времени, как правило, вероятностны и дают лишь аппроксимированное решение. Алгоритмы сублинейного времени выполнения возникают естественным образом при исследовании проверки свойств^[англ.].

Линейное время

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

Линейное время часто рассматривается как желательный атрибут алгоритма^[6]. Было проведено много исследований для создания алгоритмов с (почти) линейным или лучшим временем работы. Эти исследования включали как программные, так и аппаратные подходы. В случае аппаратного исполнения некоторые алгоритмы, которые, с математической точки зрения, никогда не могут достичь линейного времени исполнения в стандартных моделях вычислений, могут работать за линейное время. Существуют некоторые аппаратные технологии, которые используют параллельность для достижения такой цели. Примером служит ассоциативная память. Эта концепция линейного времени используется в задачах сопоставления с образцом, таких как алгоритм Бойера — Мура и алгоритм Укконена.

Квазилинейное время

Говорят, что алгоритм работает за квазилинейное время, если $T(n)=O(n\log ^{k}n)$ для некоторой константы $k$ . При $k=1$ говорят о линейно-логарифмическом времени^[7]. В терминах soft-O такое время работы записывается как ${\tilde {O}}(n)$ . Для алгоритмов с квазилинейным временем работы также верна оценка $T(n)\in o(n^{1+\varepsilon })$ для любого $\varepsilon >0$ . Таким образом, эти алгоритмы работают быстрее любого полинома от $n$ , степень которого больше $1$ .

Алгоритмы, работающие за квазилинейное время, вдобавок к линейно-логарифмическим алгоритмам, упомянутым выше, включают:

Сортировка слиянием на месте: $O(n\log ^{2}n)$ ;
Быстрая сортировка: математическое ожидание времени работы вероятностной версии алгоритма лежит в $O(n\log n)$ на любом входе, для детерминированной же версии эта оценка верна только в среднем по всем входам;
Сортировка кучей, сортировка слиянием, introsort, сортировка с помощью бинарного дерева, плавная сортировка, пасьянсная сортировка^[англ.], и другие: $O(n\log n)$ в худшем случае;
Быстрое преобразование Фурье: $O(n\log n)$ ;
Алгоритмы на матрицах Монжа: $O(n\log n)$ .

Линейно-логарифмическое время

Линейно-логарифмическое является частным случаем квазилинейного времени с показателем $k=1$ на логарифмическом множителе.

Линейно-логарифмическая функция — это функция вида $n\log n$ (то есть произведение линейного и логарифмического членов). Говорят, что алгоритм работает за линейно-логарифмическое время, если $T(n)=O(n\log n)$ ^[8]. Таким образом, линейно-логарифмическая функция растёт быстрее, чем линейная, но медленнее, чем любой многочлен от $n$ со степенью, большей $1$ .

Во многих случаях время работы $n\log n$ является просто результатом выполнения $n$ раз операции со временем работы $O(\log n)$ . Например, сортировка с помощью двоичного дерева создаёт двоичное дерево путём вставки в него каждого элемента массива размера $n$ один за другим. Поскольку операция вставки в сбалансированное бинарное дерево поиска^[англ.] занимает время $O(\log n)$ , общее время выполнения алгоритма будет линейно-логарифмическим.

Любая основанная на сравнениях сортировка^[англ.] требует по меньшей мере линейно-логарифмического числа сравнений для наихудшего случая. Одно из простых обоснований этого факта с теоретико-информационной точки зрения выглядит таким образом: в результате сортировки мы получим перестановку длины $n$ , однозначно определяющую порядок элементов. Всего есть $n!$ различных сортировок, если мы захотим однозначно закодировать каждую из них некоторой последовательностью бит, нам потребуется в среднем не меньше $\log n!\sim n\log n$ битов информации на одну перестановку. При этом результатом попарного сравнения двух элементов массива является ровно один бит информации — либо первый элемент меньше второго, либо нет. Таким образом, если мы используем только попарные сравнения для сортировки, отсортировать массив за время лучшее, чем $O(n\log n)$ в худшем случае невозможно. В то же время такая оценка на многие рекурсивные сортировки, такие как сортировка слиянием, зачастую возникает из рекуррентного уравнения $T(n)=T(n/2)+O(n)$ .

Субквадратичное время

Говорят, что алгоритм выполняется за субквадратичное время, если $T(n)=o(n^{2})$ .

Например, простые алгоритмы сортировки, основанные на сравнениях (такие как сортировка вставками), квадратичны. В то же время можно найти более продвинутые алгоритмы, которые имеют субквадратичное время выполнения (например, сортировка Шелла). Никакие сортировки общего вида не работают за линейное время, но переход от квадратичного к субквадратичному времени имеет большую практическую важность.

Полиномиальное время

Говорят, что алгоритм работает за полиномиальное время, если время работы ограничено сверху многочленом от размера входа алгоритма, то есть $T(n)=O(n^{k})$ для некоторой константы $k$ ^[1]^[9]. Задачи, для которых алгоритмы с детерминированным полиномиальным временем существуют, составляют класс сложности P, который является центральным в теории вычислительной сложности. Тезис Кобэма^[англ.] утверждает, что полиномиальное время является синонимом понятий «легко поддающийся обработке», «выполнимый», «эффективный» или «быстрый»^[10].

Некоторые примеры полиномиальных алгоритмов:

Алгоритм быстрой сортировки $n$ целых чисел делает максимум $An^{2}$ операций для некоторой константы $A$ . Таким образом, он работает за $O(n^{2})$ и является полиномиальным алгоритмом.
Все базовые арифметические операции (сложение, вычитание, умножение, деление и сравнение) могут быть выполнены за полиномиальное время.
Максимальное паросочетание в графах может быть найдено за полиномиальное время.

Строго и слабо полиномиальное время

В некоторых контекстах, особенно в оптимизации, различают алгоритмы со строгим полиномиальным временем и слабо полиномиальным временем. Эти две концепции относятся только ко входным данным, состоящим из целых чисел.

Строго полиномиальное время определяется в арифметической модели вычислений. В этой модели базовые арифметические операции (сложение, вычитание, умножение, деление и сравнение) берутся за единицы выполнения, независимо от длины операндов. Алгоритм работает в строго полиномиальное время, если^[11]

число операций в арифметической модели вычислений ограничено многочленом от числа целых во входном потоке, и
память, используемая алгоритмом, ограничена многочленом от размеров входа.

Любой алгоритм с этими двумя свойствами можно привести к алгоритму полиномиального времени путём замены арифметических операций на соответствующие алгоритмы выполнения арифметических операций на машине Тьюринга. Если второе из вышеприведённых требований не выполняется, это больше не будет верно. Если задано целое число $2^{n}$ (которое занимает память, пропорциональную n в машине Тьюринга), можно вычислить $2^{2^{n}}$ с помощью n операций, используя повторное возведение в степень. Однако память, используемая для представления $2^{2^{n}}$ , пропорциональна $2^{n}$ , и она скорее экспоненциально, чем полиномиально, зависит от памяти, используемой для входа. Отсюда — невозможно выполнить эти вычисления за полиномиальное время на машине Тьюринга, но можно выполнить за полиномиальное число арифметических операций.

Обратно — существуют алгоритмы, которые работают за число шагов машины Тьюринга, ограниченных полиномиальной длиной бинарно закодированного входа, но не работают за число арифметических операций, ограниченное многочленом от количества чисел на входе. Алгоритм Евклида для вычисления наибольшего общего делителя двух целых чисел является одним из примеров. Для двух целых чисел $a$ и $b$ время работы алгоритма ограничено $O((\log \ a+\log \ b)^{2})$ шагам машины Тьюринга. Это число является многочленом от размера бинарного представления чисел $a$ и $b$ , что грубо можно представить как $\log \ a+\log \ b$ . В то же самое время число арифметических операций нельзя ограничить числом целых во входе (что в данном случае является константой — имеется только два числа во входе). Ввиду этого замечания алгоритм не работает в строго полиномиальное время. Реальное время работы алгоритма зависит от величин $a$ и $b$ , а не только от числа целых чисел во входе.

Если алгоритм работает за полиномиальное время, но не за строго полиномиальное время, говорят, что он работает за слабо полиномиальное время^[12]. Хорошо известным примером задачи, для которой известен слабо полиномиальный алгоритм, но не известен строго полиномиальный алгоритм, является линейное программирование. Слабо полиномиальное время не следует путать с псевдополиномиальным временем.

Классы сложности

Концепция полиномиального времени приводит к нескольким классам сложности в теории сложности вычислений. Некоторые важные классы, определяемые с помощью полиномиального времени, приведены ниже.

P: Класс сложности задач разрешимости, которые могут быть решены в детерминированной машине Тьюринга за полиномиальное время.
NP: Класс сложности задач разрешимости, которые могут быть решены в недетерминированной машине Тьюринга за полиномиальное время.
ZPP: Класс сложности задач разрешимости, которые могут быть решены с нулевой ошибкой в вероятностной машине Тьюринга за полиномиальное время.
RP: Класс сложности задач разрешимости, которые могут быть решены с односторонними ошибками в вероятностной машине Тьюринга за полиномиальное время.
BPP: Класс сложности задач разрешимости, которые могут быть решены с двусторонними ошибками в вероятностной машине Тьюринга за полиномиальное время.
BQP: Класс сложности задач разрешимости, которые могут быть решены с двусторонними ошибками в квантовой машине Тьюринга за полиномиальное время.

P является наименьшим классом временной сложности на детерминированной машине, которая является устойчивой^[англ.] в терминах изменения модели машины. (Например, переход от одноленточной машины Тьюринга к мультиленточной может привести к квадратичному ускорению, но любой алгоритм, работающий за полиномиальное время на одной модели, будет работать за полиномиальное время на другой.)

Суперполиномиальное время

Говорят, что алгоритм работает за суперполиномиальное время, если T(n) не ограничен сверху полиномом. Это время равно ω(n^c) для всех констант c, где n — входной параметр, обычно — число бит входа.

Например, алгоритм, осуществляющий 2ⁿ шагов, для входа размера n требует суперполиномиального времени (конкретнее, экспоненциального времени).

Ясно, что алгоритм, использующий экспоненциальные ресурсы, суперполиномиален, но некоторые алгоритмы очень слабо суперполиномиальны. Например, тест простоты Адлемана — Померанса — Румели работает за время n^{O(log log n)} на n-битном входе. Это растёт быстрее, чем любой полином, для достаточно большого n, но размер входа должен стать очень большим, чтобы он не доминировался полиномом малой степени.

Алгоритм, требующий суперполиномиального времени, лежит вне класса сложности P. Тезис Кобэма^[англ.] утверждает, что эти алгоритмы непрактичны, и во многих случаях это так. Поскольку задача равенства классов P и NP не решена, никаких алгоритмов для решения NP-полных задач за полиномиальное время в настоящее время не известно.

Квазиполиномиальное время

Алгоритмы квазиполиномиального времени — это алгоритмы, работающие медленнее, чем за полиномиальное время, но не столь медленно, как алгоритмы экспоненциального времени. Время работы в худшем случае для квазиполиномиального алгоритма равно $2^{O((\log n)^{c})}$ для некоторого фиксированного c. Хорошо известный классический алгоритм разложения целого числа на множители, общий метод решета числового поля, который работает за время около $2^{{\tilde {O}}(n^{1/3})}$ , не является квазиполиномиальным, поскольку время работы нельзя представить как $2^{O((\log n)^{c})}$ для некоторого фиксированного c. Если константа «c» в определении алгоритма квазиполиномиального времени равна 1, мы получаем алгоритм полиномиального времени, а если она меньше 1, мы получаем алгоритм сублинейного времени.

Алгоритмы квазиполиномиального времени обычно возникают при сведении NP-трудной задачи к другой задаче. Например, можно взять NP-трудную задачу, скажем, 3SAT, и свести её к другой задаче B, но размер задачи станет равным $2^{O((\log n)^{c})}$ . В этом случае сведение не доказывает, что задача B NP-трудна, такое сведение лишь показывает, что не существует полиномиального алгоритма для B, если только не существует квазиполиномиального алгоритма для 3SAT (а тогда и для всех NP-задач). Подобным образом — существуют некоторые задачи, для которых мы знаем алгоритмы с квазиполиномиальным временем, но для которых алгоритмы с полиномиальным временем неизвестны. Такие задачи появляются в аппроксимационых алгоритмах. Знаменитый пример — ориентированная задача Штайнера, для которой существует аппроксимационный квазиполиномиальный алгоритм с аппроксимационным коэффициентом $O(\log ^{3}n)$ (где n — число вершин), но существование алгоритма с полиномиальным временем является открытой проблемой.

Класс сложности QP состоит из всех задач, имеющих алгоритмы квазиполиномиального времени. Его можно определить в терминах DTIME^[англ.] следующим образом^[13]:

{\mbox{QP}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}(2^{(\log n)^{c}})

Связь с NP-полными задачами

В теории сложности нерешённая проблема равенства классов P и NP спрашивает, не имеют ли все задачи из класса NP алгоритмы решения за полиномиальное время. Все хорошо известные алгоритмы для NP-полных задач, наподобие 3SAT, имеют экспоненциальное время. Более того, существует гипотеза, что для многих естественных NP-полных задач не существует алгоритмов с субэкспоненциальным временем выполнения. Здесь «субэкспоненциальное время» взято в смысле второго определения, приведённого ниже. (С другой стороны, многие задачи из теории графов, представленные естественным путём матрицами смежности, разрешимы за субэкспоненциальное время просто потому, что размер входа равен квадрату числа вершин.) Эта гипотеза (для задачи k-SAT) известна как гипотеза экспоненциального времени^[англ.]^[14]. Поскольку она предполагает, что NP-полные задачи не имеют алгоритмов квазиполиномиального времени, некоторые результаты неаппроксимируемости в области аппроксимационных алгоритмов исходят из того, что NP-полные задачи не имеют алгоритмов квазиполиномиального времени. Например, смотрите известные результаты по неаппроксимируемости задачи о покрытии множества.

Субэкспоненциальное время

Термин субэкспоненциальное^[англ.] время используется, чтобы выразить, что время выполнения некоторого алгоритма может расти быстрее любого полиномиального, но остаётся существенно меньше, чем экспоненциальное. В этом смысле задачи, имеющие алгоритмы субэкспоненциального времени, являются более податливыми, чем алгоритмы только с экспоненциальным временем. Точное определение «субэкспоненциальный» пока не является общепринятым^[15], и мы приводим ниже два наиболее распространённых определения.

Первое определение

Говорят, что задача решается за субэкспоненциальное время, если она решается алгоритмом, логарифм времени работы которого растёт меньше, чем любой заданный многочлен. Более точно — задача имеет субэкспоненциальное время, если для любого ε > 0 существует алгоритм, который решает задачу за время O(2^{n^ε}). Множество все таких задач составляет класс сложности SUBEXP, который в терминах DTIME можно выразить как^[3]^[16]^[17]^[18].

{\text{SUBEXP}}=\bigcap _{\varepsilon >0}{\text{DTIME}}\left(2^{n^{\varepsilon }}\right)

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

Второе определение

Некоторые авторы определяют субэкспоненциальное время как время работы 2^o(n)^[14]^[19]^[20]. Это определение допускает большее время работы, чем первое определение. Примером такого алгоритма субэкспоненциального времени служит хорошо известный классический алгоритм разложения целых чисел на множители, общий метод решета числового поля, который работает за время около $2^{{\tilde {O}}(n^{1/3})}$ , где длина входа равна n. Другим примером служит хорошо известный алгоритм для задачи изоморфизма графов^[англ.], время работы которого равно $2^{O({\sqrt {n\log n}})}$ .

Заметим, что есть разница, является ли алгоритм субэкспоненциальным по числу вершин или числу рёбер. В параметризованной сложности^[англ.] эта разница присутствует явно путём указания пары $(L,k)$ , задачи разрешимости и параметра k. SUBEPT является классом всех параметризованных задач, которые работают за субэкспоненциальное время по k и за полиномиальное по n^[21]:

{\text{SUBEPT}}={\text{DTIME}}\left(2^{o(k)}\cdot {\text{poly}}(n)\right).

Точнее, SUBEPT является классом всех параметризованных задач $(L,k)$ , для которых существует вычислимая функция $f:\mathbb {N} \to \mathbb {N}$ с $f\in o(k)$ и алгоритм, который решает L за время $2^{f(k)}\cdot {\text{poly}}(n)$ .

Гипотеза об экспоненциальном времени

Гипотеза об экспоненциальном времени ('ETH) утверждает, что 3SAT, задача выполнимости булевых формул в конъюнктивной нормальной форме с максимум тремя литералами на предложение и n переменными, не может быть решена за время 2^o(n). Точнее, гипотеза говорит, что существует некая константа c>0, такая, что 3SAT не может быть решена за время 2^cn на любой детерминированной машине Тьюринга. Если через m обозначить число предложений, ETH эквивалентна гипотезе, что k-SAT не может быть решена за время 2^o(m) для любого целого k ≥ 3^[22]. Из гипотезы об экспоненциальном времени следует, что P ≠ NP.

Экспоненциальное время

Говорят, что алгоритм работает за экспоненциальное время, если T(n) ограничено сверху значением 2^poly(n), где poly(n) — некий многочлен от n. Более формально, алгоритм работает за экспоненциальное время, если T(n) ограничено O(2^{n^k}) с некоторой константой k. Задачи, которые выполняются за экспоненциальное время на детерминированных машинах Тьюринга, образуют класс сложности EXP.

{\text{EXP}}=\bigcup _{c\in \mathbb {N} }{\text{DTIME}}\left(2^{n^{c}}\right)

Иногда термин экспоненциальное время используется для алгоритмов, для которых T(n) = 2^O(n), где показатель является не более чем линейной функцией от n. Это приводит к классу сложности E^[англ.].

{\text{E}}=\bigcup _{c\in \mathbb {N} }{\text{DTIME}}\left(2^{cn}\right)

Двойное экспоненциальное время

Говорят, что алгоритм выполняется за дважды экспоненциальное^[англ.] время, если T(n) ограничено сверху значением 2^{2^poly(n)}, где poly(n) — некоторый многочлен от n. Такие алгоритмы принадлежат классу сложности 2-EXPTIME^[англ.].

{\mbox{2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}(2^{2^{n^{c}}})

К хорошо известным дважды экспоненциальным алгоритмам принадлежат:

Процедура вычисления для арифметики Пресбургера
Вычисление базиса Грёбнера (в худшем случае^[23])
Элиминация кванторов в вещественно замкнутых полях требует как минимум дважды экспоненциальное время выполнения^[24] и может быть выполнена за это время^[25].

См. также

Примечания

↑ ¹ ² Michael Sipser. Introduction to the Theory of Computation. — Course Technology Inc, 2006. — ISBN 0-619-21764-2.
↑ Kurt Mehlhorn, Stefan Naher. Bounded ordered dictionaries in O(log log N) time and O(n) space // Information Processing Letters. — 1990. — Т. 35, вып. 4. — С. 183. — doi:10.1016/0020-0190(90)90022-P.
↑ ¹ ² László Babai, Lance Fortnow, N. Nisan, Avi Wigderson. BPP has subexponential time simulations unless EXPTIME has publishable proofs // Computational Complexity. — Berlin, New York: Springer-Verlag, 1993. — Т. 3, вып. 4. — С. 307—318. — doi:10.1007/BF01275486.
↑ J. E. Rawlins, Gregory E. Shannon. Efficient Matrix Chain Ordering in Polylog Time // SIAM Journal on Computing. — Philadelphia: Society for Industrial and Applied Mathematics, 1998. — Т. 27, вып. 2. — С. 466—490. — ISSN 1095-7111. — doi:10.1137/S0097539794270698.
↑ Ravi Kumar, Ronitt Rubinfeld. Sublinear time algorithms // SIGACT News. — 2003. — Т. 34, вып. 4. — С. 57—67. — doi:10.1145/954092.954103.
↑ DR K N PRASANNA KUMAR, PROF B S KIRANAGI AND PROF C S BAGEWADI. A GENERAL THEORY OF THE SYSTEM ‘QUANTUM INFORMATION - QUANTUM ENTANGLEMENT, SUBATOMIC PARTICLE DECAY – ASYMMETRIC SPIN STATES, NON LOCALLY HIDDEN VARIABLES – A CONCATENATED MODEL // International Journal of Scientific and Research Publications. — July 2012. — Т. 2, вып. 7. — ISSN 22503153.
↑ Ashish V. Naik, Kenneth W. Regan, D. Sivakumar. On Quasilinear Time Complexity Theory (англ.) // Theoretical Computer Science^[англ.]. — Vol. 148. — P. 325—349.
↑ Sedgewick, R. and Wayne K (2011). Algorithms, 4th Ed Архивная копия от 15 июля 2014 на Wayback Machine. p. 186. Pearson Education, Inc.
↑ Christos H. Papadimitriou. Computational complexity. — Reading, Mass.: Addison-Wesley, 1994. — ISBN 0-201-53082-1.
↑ Alan Cobham. Proc. Logic, Methodology, and Philosophy of Science II. — North Holland, 1965. — С. The intrinsic computational difficulty of functions.
↑ Martin Grötschel, László Lovász, Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization. — Springer, 1988. — С. Complexity, Oracles, and Numerical Computation. — ISBN 0-387-13624-X.
↑ Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. — Springer, 2003. — Т. 1. — С. Preliminaries on algorithms and Complexity. — ISBN 3-540-44389-4.
↑ Complexity Zoo Архивная копия от 26 июля 2010 на Wayback Machine Class QP: Quasipolynomial-Time Архивная копия от 22 декабря 2015 на Wayback Machine
↑ ¹ ² R. Impagliazzo, R. Paturi. On the complexity of k-SAT // Journal of Computer and System Sciences. — Elsevier, 2001. — Т. 62, вып. 2. — С. 367—375. — ISSN 1090-2724. — doi:10.1006/jcss.2000.1727.
↑ Aaronson, Scott. A not-quite-exponential dilemma. — 5 April 2009.
↑ Complexity Zoo Архивная копия от 26 июля 2010 на Wayback Machine Class SUBEXP: Deterministic Subexponential-Time Архивная копия от 27 августа 2016 на Wayback Machine
↑ P. Moser. Baire's Categories on Small Complexity Classes // Lecture Notes in Computer Science. — Berlin, New York: Springer-Verlag, 2003. — С. 333—342. — ISSN 0302-9743.
↑ P.B. Miltersen. DERANDOMIZING COMPLEXITY CLASSES // Handbook of Randomized Computing. — Kluwer Academic Pub, 2001. — С. 843.
↑ Greg Kuperberg. A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem // SIAM Journal on Computing. — Philadelphia: Society for Industrial and Applied Mathematics, 2005. — Т. 35, вып. 1. — С. 188. — ISSN 1095-7111. — doi:10.1137/s0097539703436345.
↑ Oded Regev. A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space. — 2004.
↑ Jörg Flum, Martin Grohe. Parameterized Complexity Theory. — Springer, 2006. — С. 417. — ISBN 978-3-540-29952-3. Архивировано 18 ноября 2007 года.
↑ R. Impagliazzo, R. Paturi, F. Zane. Which problems have strongly exponential complexity? // Journal of Computer and System Sciences. — 2001. — Т. 63, вып. 4. — С. 512—530. — doi:10.1006/jcss.2001.1774.
↑ Mayr,E. & Mayer,A. The Complexity of the Word Problem for Commutative Semi-groups and Polynomial Ideals // Adv. in Math.. — 1982. — Вып. 46. — С. 305—329.
↑ J.H. Davenport, J. Heintz. Real Quantifier Elimination is Doubly Exponential // J. Symbolic Comp.. — 1988. — Вып. 5. — С. 29—35..
↑ G.E. Collins. Proc. 2nd. GI Conference Automata Theory & Formal Languages. — Springer. — Т. 33. — С. 134—183. — (Lecture Notes in Computer Science).

[Sipser-1] ¹ ² Michael Sipser. Introduction to the Theory of Computation. — Course Technology Inc, 2006. — ISBN 0-619-21764-2.

[2] Kurt Mehlhorn, Stefan Naher. Bounded ordered dictionaries in O(log log N) time and O(n) space // Information Processing Letters. — 1990. — Т. 35, вып. 4. — С. 183. — doi:10.1016/0020-0190(90)90022-P.

[bpp-3] ¹ ² László Babai, Lance Fortnow, N. Nisan, Avi Wigderson. BPP has subexponential time simulations unless EXPTIME has publishable proofs // Computational Complexity. — Berlin, New York: Springer-Verlag, 1993. — Т. 3, вып. 4. — С. 307—318. — doi:10.1007/BF01275486.

[4] J. E. Rawlins, Gregory E. Shannon. Efficient Matrix Chain Ordering in Polylog Time // SIAM Journal on Computing. — Philadelphia: Society for Industrial and Applied Mathematics, 1998. — Т. 27, вып. 2. — С. 466—490. — ISSN 1095-7111. — doi:10.1137/S0097539794270698.

[5] Ravi Kumar, Ronitt Rubinfeld. Sublinear time algorithms // SIGACT News. — 2003. — Т. 34, вып. 4. — С. 57—67. — doi:10.1145/954092.954103.

[6] DR K N PRASANNA KUMAR, PROF B S KIRANAGI AND PROF C S BAGEWADI. A GENERAL THEORY OF THE SYSTEM ‘QUANTUM INFORMATION - QUANTUM ENTANGLEMENT, SUBATOMIC PARTICLE DECAY – ASYMMETRIC SPIN STATES, NON LOCALLY HIDDEN VARIABLES – A CONCATENATED MODEL // International Journal of Scientific and Research Publications. — July 2012. — Т. 2, вып. 7. — ISSN 22503153.

[7] Ashish V. Naik, Kenneth W. Regan, D. Sivakumar. On Quasilinear Time Complexity Theory (англ.) // Theoretical Computer Science^[англ.]. — Vol. 148. — P. 325—349.

[8] Sedgewick, R. and Wayne K (2011). Algorithms, 4th Ed Архивная копия от 15 июля 2014 на Wayback Machine. p. 186. Pearson Education, Inc.

[9] Christos H. Papadimitriou. Computational complexity. — Reading, Mass.: Addison-Wesley, 1994. — ISBN 0-201-53082-1.

[10] Alan Cobham. Proc. Logic, Methodology, and Philosophy of Science II. — North Holland, 1965. — С. The intrinsic computational difficulty of functions.

[11] Martin Grötschel, László Lovász, Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization. — Springer, 1988. — С. Complexity, Oracles, and Numerical Computation. — ISBN 0-387-13624-X.

[12] Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. — Springer, 2003. — Т. 1. — С. Preliminaries on algorithms and Complexity. — ISBN 3-540-44389-4.

[13] Complexity Zoo Архивная копия от 26 июля 2010 на Wayback Machine Class QP: Quasipolynomial-Time Архивная копия от 22 декабря 2015 на Wayback Machine

[ETH-14] ¹ ² R. Impagliazzo, R. Paturi. On the complexity of k-SAT // Journal of Computer and System Sciences. — Elsevier, 2001. — Т. 62, вып. 2. — С. 367—375. — ISSN 1090-2724. — doi:10.1006/jcss.2000.1727.

[15] Aaronson, Scott. A not-quite-exponential dilemma. — 5 April 2009.

[16] Complexity Zoo Архивная копия от 26 июля 2010 на Wayback Machine Class SUBEXP: Deterministic Subexponential-Time Архивная копия от 27 августа 2016 на Wayback Machine

[17] P. Moser. Baire's Categories on Small Complexity Classes // Lecture Notes in Computer Science. — Berlin, New York: Springer-Verlag, 2003. — С. 333—342. — ISSN 0302-9743.

[18] P.B. Miltersen. DERANDOMIZING COMPLEXITY CLASSES // Handbook of Randomized Computing. — Kluwer Academic Pub, 2001. — С. 843.

[19] Greg Kuperberg. A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem // SIAM Journal on Computing. — Philadelphia: Society for Industrial and Applied Mathematics, 2005. — Т. 35, вып. 1. — С. 188. — ISSN 1095-7111. — doi:10.1137/s0097539703436345.

[20] Oded Regev. A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space. — 2004.

[21] Jörg Flum, Martin Grohe. Parameterized Complexity Theory. — Springer, 2006. — С. 417. — ISBN 978-3-540-29952-3. Архивировано 18 ноября 2007 года.

[22] R. Impagliazzo, R. Paturi, F. Zane. Which problems have strongly exponential complexity? // Journal of Computer and System Sciences. — 2001. — Т. 63, вып. 4. — С. 512—530. — doi:10.1006/jcss.2001.1774.

[23] Mayr,E. & Mayer,A. The Complexity of the Word Problem for Commutative Semi-groups and Polynomial Ideals // Adv. in Math.. — 1982. — Вып. 46. — С. 305—329.

[24] J.H. Davenport, J. Heintz. Real Quantifier Elimination is Doubly Exponential // J. Symbolic Comp.. — 1988. — Вып. 5. — С. 29—35..

[25] G.E. Collins. Proc. 2nd. GI Conference Automata Theory & Formal Languages. — Springer. — Т. 33. — С. 134—183. — (Lecture Notes in Computer Science).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]