Сложность времени

Графики функций, обычно используемых при анализе алгоритмов , показывающие количество операций N в зависимости от размера входных данных n для каждой функции

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

Поскольку время работы алгоритма может различаться для разных входов одного и того же размера, обычно рассматривают наихудшую временную сложность , которая представляет собой максимальное количество времени, требуемое для входов заданного размера. Менее распространенной и обычно указываемой явно является средняя сложность , которая представляет собой среднее время, затрачиваемое на вводы заданного размера (это имеет смысл, поскольку существует только конечное число возможных вводов заданного размера). В обоих случаях временная сложность обычно выражается как функция размера входных данных. ^[1]^{: 226}Поскольку эту функцию обычно трудно вычислить точно, а время выполнения небольших входных данных обычно не имеет никакого значения, обычно фокусируется на поведении сложности при увеличении размера входных данных, то есть на асимптотическом поведении сложности. Следовательно, временная сложность обычно выражается с использованием нотации большой буквы O , обычно ${\ Displaystyle О (п)}$ , ${\ Displaystyle О (п \ журнал п)}$ , ${\ Displaystyle О (п ^ {\ альфа})}$ , ${\ Displaystyle О (2 ^ {п})}$ и т. д., где $n$ - размер входных данных в битах, необходимых для представления входных данных.

Алгоритмические сложности классифицируются в соответствии с типом функции, обозначенной большой нотацией O. Например, алгоритм с временной сложностью ${\ Displaystyle О (п)}$ это линейный алгоритм времени и алгоритм с временной сложностью ${\ Displaystyle О (п ^ {\ альфа})}$ для некоторой постоянной ${\ displaystyle \ alpha> 1}$ представляет собой алгоритм с полиномиальным временем .

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

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

Имя	Класс сложности	Время работы ( T ( n ))	Примеры времени работы	Примеры алгоритмов
постоянное время		О (1)	10	Нахождение медианного значения в отсортированном массиве чисел Вычисляя $(-1) n$
обратное время Аккермана		О ( а ( п ))		Амортизированное время на операцию с использованием непересекающегося набора
повторное логарифмическое время		O ( журнал * n )		Распределенная раскраска циклов
логарифмический		O (журнал журнал n )		Амортизированное время на операцию с использованием очереди с ограниченным приоритетом ^[2]
логарифмическое время	DLOGTIME	O (журнал n )	журнал n , журнал ( n ² )	Бинарный поиск
полилогарифмическое время		поли (журнал п )	(журнал n ) ²
дробная мощность		$O (n c),$ где $0 < c <1$	п ^1/2 , п ^2/3	Поиск в kd-дереве
линейное время		О ( п )	п , 2 п + 5	Поиск наименьшего или наибольшего элемента в несортированном массиве , алгоритм Кадане , линейный поиск
"n log-star n" раз		O ( п журнал * п )		Зайдель «s многоугольник триангуляции алгоритм.
линейное время		O ( п войти п )	п войти п , журнал п !	Самая быстрая сортировка сравнения ; Быстрое преобразование Фурье .
квазилинейное время		п поли (журнал п )
квадратичное время		О ( п ² )	п ²	Пузырьковая сортировка ; Вставка сортировки ; Прямая свертка
кубическое время		О ( п ³ )	п ³	Простое умножение двух матриц размера n × n . Расчет частичной корреляции .
полиномиальное время	п	2 ^{O (журнал п )} = поли ( п )	п ² + п , п ¹⁰	Алгоритм Кармаркара для линейного программирования ; Тест простоты AKS ^[3]^[4]
квазиполиномиальное время	QP	2 ^{поли (log n )}	n ^{журнал журнал n} , n ^{журнал n}	Самый известный O (log ² n ) - алгоритм аппроксимации для задачи ориентированного дерева Штейнера .
субэкспоненциальное время (первое определение)	СУБЭКСП	O (2 ^{n ^ε} ) для всех ε > 0		Содержит BPP, если EXPTIME (см. Ниже) не равен MA . ^[5]
субэкспоненциальное время (второе определение)		2 ^{о ( п )}	2 ^{п ^1/3}	Лучший известный алгоритм для целочисленной факторизации ; ранее лучший алгоритм для изоморфизма графов
экспоненциальное время (с линейным показателем)	E	2 ^{О ( п )}	1.1 ^п , 10 ^п	Решение задачи коммивояжера с помощью динамического программирования
экспоненциальное время	EXPTIME	2 ^{поли ( n )}	2 ^п , 2 ^{п ²}	Решение умножения цепочки матриц с помощью перебора
факториальное время		О ( п !)	п !	Решение задачи коммивояжера с помощью поиска перебора
двойное экспоненциальное время	2-ВРЕМЯ	2 ^{2 ^{поли ( п )}}	2 ^{2 ^п}	Определение истинности данного утверждения в арифметике Пресбургера

Постоянное время

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

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

Вот несколько примеров фрагментов кода, которые выполняются в постоянное время:

int index = 5;
int item = список [индекс];если (условие истинно) то выполнить некоторую операцию, которая выполняется в постоянное времяеще выполнить некоторую другую операцию, которая выполняется в постоянное времядля i = от 1 до 100 для j = от 1 до 200 выполнить некоторую операцию, которая выполняется в постоянное время

Если T ( n ) равно O ( любое постоянное значение ), это эквивалентно и указано в стандартных обозначениях как T ( n ), равное O (1).

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

Говорят, что алгоритм принимает логарифмическое время, когда T ( n ) = O (log n ) . Поскольку log _a n и log _b n связаны постоянным множителем , и такой множитель не имеет отношения к классификации большого O, стандартное использование алгоритмов логарифмического времени - O (log n ) независимо от основания логарифма, появляющегося в выражение Т .

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

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

Пример логарифмического времени дается поиском по словарю. Рассмотрим словарь $D,$ содержащий n статей, отсортированных в алфавитном порядке . Мы предполагаем, что для $1 \leq k \leq n$ можно получить доступ к $k-$ й записи словаря за постоянное время. Пусть $D (k)$ обозначает эту $k-$ ю запись. Согласно этим гипотезам, проверка того, есть ли слово $w$ в словаре, может выполняться за логарифмическое время: рассмотрим ${\ Displaystyle D (\ lfloor п / 2 \ rfloor)}$ , где ${\ Displaystyle \ lfloor \; \ rfloor}$ обозначает функцию пола . Если ${\ Displaystyle ш = D (\ lfloor п / 2 \ rfloor)}$ , тогда все готово. В противном случае, если ${\ Displaystyle ш <D (\ lfloor п / 2 \ rfloor)}$ , продолжите поиск таким же образом в левой половине словаря, в противном случае продолжите аналогично с правой половиной словаря. Этот алгоритм похож на метод, который часто используется для поиска статьи в бумажном словаре.

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

Говорят, что алгоритм работает за полилогарифмическое время, если его время $T (n)$ равно $O ((log n) k)$ для некоторой константы k . Другой способ записать это - $O (log k n)$ .

Например, упорядочение цепи , матрица может быть решено в полилогарифмическим время на параллельной машине с произвольным доступом , ^[6] , и график может быть определен , чтобы быть плоскими в полном динамическом пути в O (вход ³ н ) по времени на вставку / операция удаления . ^[7]

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

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

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

Конкретный термин « алгоритм сублинейного времени» обычно зарезервирован для алгоритмов, которые отличаются от приведенных выше в том, что они запускаются на классических моделях последовательных машин и не допускают предварительных предположений на входе. ^{[8] Однако} они могут быть рандомизированы и действительно должны быть рандомизированы для всех, кроме самых тривиальных задач.

Поскольку такой алгоритм должен давать ответ без чтения всего ввода, его особенности сильно зависят от доступа, разрешенного к вводу. Обычно для входа, представленного в виде двоичной строки b ₁ ,…, b _k, предполагается, что алгоритм может за время O (1) запросить и получить значение b _i для любого i .

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

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

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

Линейное время - это наилучшая временная сложность в ситуациях, когда алгоритм должен последовательно считывать все входные данные. Поэтому много исследований было вложено в открытие алгоритмов, показывающих линейное время или, по крайней мере, почти линейное время. Это исследование включает как программные, так и аппаратные методы. Для этого существует несколько аппаратных технологий, использующих параллелизм . Примером является память с адресацией по содержимому . Эта концепция линейного времени используется в алгоритмах строка соответствия , такие как алгоритм Бойера-Мура и алгоритм Укконена .

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

Говорят, что алгоритм работает в квазилинейном времени (также называемом логлинейным временем ), если T ( n ) = O ( n log ^k n ) для некоторой положительной константы k ; ^[9] линейное время - это случай k = 1 . ^[10] Используя мягкую нотацию O, эти алгоритмы имеют вид Õ ( n ). Алгоритмы квазилинейного времени также O ( n ^{1+ ε} ) для любой константы ε > 0,и, таким образом, работает быстрее, чем любой алгоритм с полиномиальным временем, чья временная граница включает член n ^c для любого c > 1 .

Алгоритмы, работающие в квазилинейном времени, включают:

Сортировка слиянием на месте , O ( n log ² n )
Quicksort , O ( n log n ), в его рандомизированной версии, имеет время выполнения, равное O ( n log n ) в ожидании на входе наихудшего случая. Его нерандомизированная версия имеет время работы O ( n log n ) только с учетом средней сложности случая.
Пирамидальная сортировка , O ( п журнал п ), сортировка слияние , introsort , бинарное дерево сортировки, Плавная сортировка , терпение сортировки и т.д. в худшем случае
Быстрые преобразования Фурье , O ( n log n )
Расчет массива Монжа , O ( n log n )

Во многих случаях время выполнения n log n является просто результатом выполнения операции Θ (log n ) n раз (обозначения см. В разделе «Обозначение Big O» § Семейство обозначений Бахмана – Ландау ). Например, сортировка двоичного дерева создает двоичное дерево , вставляя каждый элемент массива размером n один за другим. Поскольку операция вставки в самобалансирующееся двоичное дерево поиска занимает время O (log n ), весь алгоритм занимает время O ( n log n ) .

Сортировка сравнений требует как минимум Ω ( n log n ) сравнений в худшем случае, потому что log ( n !) = Θ ( n log n ) по приближению Стирлинга . Они также часто возникают из рекуррентного соотношения T ( n ) = 2 T ( n / 2) + O ( n ) .

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

Алгоритм называется subquadratic время , если Т ( п ) = О ( п ² ) .

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

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

Алгоритм называется быть полиномиальное время , если его продолжительность будет ограничена сверху с помощью полиномиального выражения в размере входных данных для алгоритма, то есть, Т ( п ) = О ( п ^к ) для некоторой положительной константы к . ^[1]^[11] Задачи, для которых существует детерминированный алгоритм с полиномиальным временем, относятся к классу сложности P , который является центральным в области теории сложности вычислений . Тезис Кобхэмаутверждает, что полиномиальное время является синонимом слов «послушный», «выполнимый», «эффективный» или «быстрый». ^[12]

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

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

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

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

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

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

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

И наоборот, есть алгоритмы, которые выполняются за несколько шагов машины Тьюринга, ограниченных полиномом от длины двоично-кодированных входных данных, но не выполняют количество арифметических операций, ограниченных полиномом от количества входных чисел. Алгоритм Евклида для вычисления наибольшего общего делителя двух целых чисел является одним из примеров. Учитывая два целых числа ${\ displaystyle a}$ и ${\ displaystyle b}$ , алгоритм выполняет ${\ Displaystyle О (\ журнал а + \ журнал б)}$ арифметические операции над числами с не более чем ${\ Displaystyle О (\ журнал а + \ журнал б)}$ биты. В то же время количество арифметических операций не может быть ограничено количеством целых чисел во входных данных (которое в данном случае постоянно, во входных данных всегда только два целых числа). Из-за последнего наблюдения алгоритм не работает за строго полиномиальное время. Его реальное время работы зависит от величины ${\ displaystyle a}$ и ${\ displaystyle b}$ и не только от количества целых чисел во входных данных.

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

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

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

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

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

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

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

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

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

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

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

Алгоритмы квазиполиномиального времени - это алгоритмы, которые работают дольше, чем полиномиальное время, но не настолько долго, чтобы быть экспоненциальным временем. Наихудшее время работы квазиполиномиального алгоритма времени составляет ${\ Displaystyle 2 ^ {О (\ журнал ^ {с} п)}}$ для некоторых фиксированных ${\ displaystyle c> 0}$ . Для ${\ displaystyle c = 1}$ мы получаем алгоритм полиномиального времени, для ${\ displaystyle c <1}$ мы получаем алгоритм сублинейного времени.

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

Другие вычислительные задачи с квазиполиномиальными временными решениями, но без известного полиномиального временного решения, включают задачу с установленной кликой, в которой цель состоит в том, чтобы найти большую клику в объединении клики и случайного графа . Хотя квазиполиномиально разрешима, было высказано предположение, что проблема насаждаемой клики не имеет решения за полиномиальное время; Эта гипотеза насаждаемой клики использовалась в качестве предположения о вычислительной сложности, чтобы доказать сложность ряда других проблем в теории вычислительных игр , тестировании свойств и машинном обучении . ^[15]

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

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

Отношение к NP-полным задачам

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

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

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

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

Проблема называется субэкспоненциальной разрешимой во времени, если ее можно решить за время выполнения, логарифмы которого становятся меньше любого заданного полинома. Точнее, проблема находится в субэкспоненциальном времени, если для каждого ε > 0 существует алгоритм, который решает задачу за время O (2 ^{n ^ε} ). Набор всех таких проблем представляет собой класс сложности SUBEXP, который можно определить в терминах DTIME следующим образом. ^[5]^[19]^[20]^[21]

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

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

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

Некоторые авторы определяют субэкспоненциальное время как время работы в 2 ^{o ( n )} . ^[17]^[22]^[23] Это определение допускает большее время работы, чем первое определение субэкспоненциального времени. Примером такого алгоритма субэкспоненциального времени является наиболее известный классический алгоритм целочисленной факторизации, решето общего числового поля , которое выполняется за время примерно ${\ Displaystyle 2 ^ {{\ тильда {O}} (п ^ {1/3})}}$ , где длина входа равна n . Другим примером была проблема изоморфизма графов , которую самый известный алгоритм с 1982 по 2016 год решал в ${\ displaystyle 2 ^ {O \ left ({\ sqrt {n \ log n}} \ right)}}$ . Однако на STOC 2016 был представлен алгоритм квазиполиномиального времени. ^[24]

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

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

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

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

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

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

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

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

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

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

Факториальное время

Примером алгоритма, работающего в факториальном времени, является bogosort , заведомо неэффективный алгоритм сортировки, основанный на пробах и ошибках . Богосорт сортирует список из n элементов, многократно перетасовывая список, пока не будет обнаружено, что он отсортирован. В среднем случае каждый проход алгоритма богосорта будет проверять один из n ! заказы из n элементов. Если элементы различны, сортируется только один такой порядок. Богосорт разделяет наследие с теоремой о бесконечной обезьяне .

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

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

{\ displaystyle {\ mbox {2-EXPTIME}} = \ bigcup _ {c \ in \ mathbb {N}} {\ mbox {DTIME}} \ left (2 ^ {2 ^ {n ^ {c}}} \ верно)}

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

Процедуры принятия решений для арифметики Пресбургера
Вычисление базиса Грёбнера (в худшем случае ^[27] )
Исключение кванторов на реальных замкнутых полях занимает как минимум удвоенное экспоненциальное время ^[28] и может быть выполнено за это время. ^[29]

См. Также

L-обозначение
Космическая сложность

Ссылки

^ a b Сипсер, Майкл (2006). Введение в теорию вычислений . ISBN курса Technology Inc. 0-619-21764-2.
^ Мельхорн, Курт ; Нахер, Стефан (1990). «Ограниченные упорядоченные словари во времени $O$ $(log log$ $N$ $)$ и $O$ $($ $n$ $)$ пространстве». Письма об обработке информации . 35 (4): 183–189. DOI : 10.1016 / 0020-0190 (90) 90022-P .
^ Тао, Теренс (2010). «1.11 Тест на простоту AKS» . Эпсилон комнаты, II: страницы третьего года математического блога . Аспирантура по математике. 117 . Провиденс, Род-Айленд: Американское математическое общество. С. 82–86. DOI : 10,1090 / г / м2 / 117 . ISBN 978-0-8218-5280-4. Руководство по ремонту 2780010 .
^ Ленстра, HW младший ; Померанс, Карл (2019). «Проверка на простоту с гауссовскими периодами» (PDF) . Журнал Европейского математического общества . 21 (4): 1229–1269. DOI : 10.4171 / Jems / 861 . Руководство по ремонту 3941463 .
^ а б Бабай, Ласло ; Фортноу, Лэнс ; Nisan, N .; Вигдерсон, Ави (1993). «BPP имеет субэкспоненциальное моделирование времени, если EXPTIME не имеет опубликованных доказательств». Вычислительная сложность . Берлин, Нью-Йорк: Springer-Verlag . 3 (4): 307–318. DOI : 10.1007 / BF01275486 .
^ Брэдфорд, Филипп G .; Роулинз, Грегори Дж. Э .; Шеннон, Грегори Э. (1998). «Эффективное упорядочивание цепочек матриц за время полилога». SIAM Journal on Computing . 27 (2): 466–490. DOI : 10,1137 / S0097539794270698 . Руководство по ремонту 1616556 .
^ Холм, Джейкоб; Ротенберг, Ева (2020). «Полностью динамическое испытание планарности в полилогарифмическом времени». У Макарычева Константин; Макарычев Юрий; Тулсиани, Мадхур; Каматх, Гаутам; Чужой, Юлия (ред.). Труды 52 - й ежегодный ACM SIGACT симпозиум по теории вычислений, STOC 2020, Чикаго, Иллинойс, США, 22-26 июня 2020 года . Ассоциация вычислительной техники. С. 167–180. arXiv : 1911.03449 . DOI : 10.1145 / 3357713.3384249 .
^ Кумар, Рави; Рубинфельд, Ронитт (2003). «Алгоритмы сублинейного времени» (PDF) . Новости SIGACT . 34 (4): 57–67. DOI : 10.1145 / 954092.954103 .
^ Наик, Ашиш В .; Риган, Кеннет У .; Сивакумар, Д. (1995). «К теории квазилинейной сложности» (PDF) . Теоретическая информатика . 148 (2): 325–349. DOI : 10.1016 / 0304-3975 (95) 00031-Q . Руководство по ремонту 1355592 .
^ Седжвик, Роберт; Уэйн, Кевин (2011). Алгоритмы (4-е изд.). Pearson Education. п. 186.
^ Пападимитриу, Христос Х. (1994). Вычислительная сложность . Ридинг, Массачусетс: Эддисон-Уэсли. ISBN 0-201-53082-1.
^ Кобэм, Алан (1965). «Внутренняя вычислительная сложность функций». Proc. Логика, методология и философия науки II . Северная Голландия.
^ Grötschel, Мартин ; Ласло Ловас ; Александр Шрайвер (1988). «Сложность, оракулы и численные вычисления». Геометрические алгоритмы и комбинаторная оптимизация . Springer. ISBN 0-387-13624-X.
^ Шрайвер, Александр (2003). «Предварительные сведения об алгоритмах и сложности». Комбинаторная оптимизация: многогранники и эффективность . 1 . Springer. ISBN 3-540-44389-4.
^ Браверман, Марк ; Кун-Ко, Янг; Рубинштейн, Авиад; Вайнштейн, Омри (2017). «Твердость ETH для плотного $k$ -подграфа с идеальной полнотой». В Klein, Филип Н. (ред.). Материалы двадцать восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA 2017, Барселона, Испания, отель Porta Fira, 16-19 января . Общество промышленной и прикладной математики. С. 1326–1341. arXiv : 1504.08352 . DOI : 10.1137 / 1.9781611974782.86 . Руководство по ремонту 3627815 .
^ Зоопарк сложности : класс QP: квазиполиномиальное время
^ a b Impagliazzo, Рассел ; Патури, Рамамохан (2001). «О сложности k -SAT» (PDF) . Журнал компьютерных и системных наук . 62 (2): 367–375. DOI : 10,1006 / jcss.2000.1727 . Руководство по ремонту 1820597 .
↑ Ааронсон, Скотт (5 апреля 2009 г.). «Не совсем экспоненциальная дилемма» . Штетл-Оптимизированный . Проверено 2 декабря 2009 года .
^ Зоопарк сложности : класс SUBEXP: детерминированная субэкспоненциально-временная
^ Мозер, П. (2003). «Категории Бэра по классам малой сложности». В Анджей Лингас; Бенгт Дж. Нильссон (ред.). Основы теории вычислений: 14-й Международный симпозиум, FCT 2003, Мальмё, Швеция, 12-15 августа 2003 г., Труды . Конспект лекций по информатике . 2751 . Берлин, Нью-Йорк: Springer-Verlag. С. 333–342. DOI : 10.1007 / 978-3-540-45077-1_31 . ISBN 978-3-540-40543-6. ISSN 0302-9743 .
^ Miltersen, РВ (2001). «Дерандомизация классов сложности». Справочник по рандомизированным вычислениям . Комбинаторная оптимизация. Kluwer Academic Pub. 9 : 843. DOI : 10.1007 / 978-1-4615-0013-1_19 . ISBN 978-1-4613-4886-3.
^ Куперберг, Грег (2005). "Субэкспоненциальный квантовый алгоритм для проблемы диэдральной скрытой подгруппы". SIAM Journal on Computing . Филадельфия. 35 (1): 188. arXiv : Quant-ph / 0302112 . DOI : 10.1137 / s0097539703436345 . ISSN 1095-7111 .
↑ Одед Регев (2004). "Субэкспоненциальный алгоритм времени для задачи о диэдральной скрытой подгруппе с полиномиальным пространством". arXiv : Quant-ph / 0406151v1 .
^ Grohe, Мартин; Нойен, Даниэль (2021). "Последние достижения в проблеме изоморфизма графов". arXiv : 2011.01366 . Цитировать журнал требует |journal=( помощь )
^ Флум, Йорг; Grohe, Мартин (2006). Параметризованная теория сложности . Springer. п. 417. ISBN 978-3-540-29952-3.
^ Impagliazzo, R .; Paturi, R .; Зейн, Ф. (2001). «Какие проблемы имеют сильно экспоненциальную сложность?» . Журнал компьютерных и системных наук . 63 (4): 512–530. DOI : 10,1006 / jcss.2001.1774 .
^ Майр, Эрнст В .; Мейер, Альберт Р. (1982). «Сложность словесных задач для коммутативных полугрупп и полиномиальных идеалов» . Успехи в математике . 46 (3): 305–329. DOI : 10.1016 / 0001-8708 (82) 90048-2 . Руководство по ремонту 0683204 .
^ Дэвенпорт, Джеймс Х .; Хайнц, Джоос (1988). «Исключение реального квантора двояко экспоненциально» . Журнал символических вычислений . 5 (1-2): 29–35. DOI : 10.1016 / S0747-7171 (88) 80004-X . Руководство по ремонту 0949111 .
^ Коллинз, Джордж Э. (1975). «Исключение кванторов для вещественных замкнутых полей цилиндрическим алгебраическим разложением». В Брахаге, Х. (ред.). Теория автоматов и формальных Языки: вторая GI конференция, Кайзерслаутерн, 20-23 мая, 1975 . Конспект лекций по информатике. 33 . Springer. С. 134–183. DOI : 10.1007 / 3-540-07407-4_17 . Руководство по ремонту 0403962 .

[Sipser-1] Сипсер, Майкл (2006). Введение в теорию вычислений . ISBN курса Technology Inc. 0-619-21764-2.

[2] Мельхорн, Курт ; Нахер, Стефан (1990). «Ограниченные упорядоченные словари во времени $O$ $(log log$ $N$ $)$ и $O$ $($ $n$ $)$ пространстве». Письма об обработке информации . 35 (4): 183–189. DOI : 10.1016 / 0020-0190 (90) 90022-P .

[tao-aks-3] Тао, Теренс (2010). «1.11 Тест на простоту AKS» . Эпсилон комнаты, II: страницы третьего года математического блога . Аспирантура по математике. 117 . Провиденс, Род-Айленд: Американское математическое общество. С. 82–86. DOI : 10,1090 / г / м2 / 117 . ISBN 978-0-8218-5280-4. Руководство по ремонту 2780010 .

[4] Ленстра, HW младший ; Померанс, Карл (2019). «Проверка на простоту с гауссовскими периодами» (PDF) . Журнал Европейского математического общества . 21 (4): 1229–1269. DOI : 10.4171 / Jems / 861 . Руководство по ремонту 3941463 .

[bpp-5] а б Бабай, Ласло ; Фортноу, Лэнс ; Nisan, N .; Вигдерсон, Ави (1993). «BPP имеет субэкспоненциальное моделирование времени, если EXPTIME не имеет опубликованных доказательств». Вычислительная сложность . Берлин, Нью-Йорк: Springer-Verlag . 3 (4): 307–318. DOI : 10.1007 / BF01275486 .

[6] Брэдфорд, Филипп G .; Роулинз, Грегори Дж. Э .; Шеннон, Грегори Э. (1998). «Эффективное упорядочивание цепочек матриц за время полилога». SIAM Journal on Computing . 27 (2): 466–490. DOI : 10,1137 / S0097539794270698 . Руководство по ремонту 1616556 .

[7] Холм, Джейкоб; Ротенберг, Ева (2020). «Полностью динамическое испытание планарности в полилогарифмическом времени». У Макарычева Константин; Макарычев Юрий; Тулсиани, Мадхур; Каматх, Гаутам; Чужой, Юлия (ред.). Труды 52 - й ежегодный ACM SIGACT симпозиум по теории вычислений, STOC 2020, Чикаго, Иллинойс, США, 22-26 июня 2020 года . Ассоциация вычислительной техники. С. 167–180. arXiv : 1911.03449 . DOI : 10.1145 / 3357713.3384249 .

[8] Кумар, Рави; Рубинфельд, Ронитт (2003). «Алгоритмы сублинейного времени» (PDF) . Новости SIGACT . 34 (4): 57–67. DOI : 10.1145 / 954092.954103 .

[9] Наик, Ашиш В .; Риган, Кеннет У .; Сивакумар, Д. (1995). «К теории квазилинейной сложности» (PDF) . Теоретическая информатика . 148 (2): 325–349. DOI : 10.1016 / 0304-3975 (95) 00031-Q . Руководство по ремонту 1355592 .

[10] Седжвик, Роберт; Уэйн, Кевин (2011). Алгоритмы (4-е изд.). Pearson Education. п. 186.

[11] Пападимитриу, Христос Х. (1994). Вычислительная сложность . Ридинг, Массачусетс: Эддисон-Уэсли. ISBN 0-201-53082-1.

[12] Кобэм, Алан (1965). «Внутренняя вычислительная сложность функций». Proc. Логика, методология и философия науки II . Северная Голландия.

[13] Grötschel, Мартин ; Ласло Ловас ; Александр Шрайвер (1988). «Сложность, оракулы и численные вычисления». Геометрические алгоритмы и комбинаторная оптимизация . Springer. ISBN 0-387-13624-X.

[14] Шрайвер, Александр (2003). «Предварительные сведения об алгоритмах и сложности». Комбинаторная оптимизация: многогранники и эффективность . 1 . Springer. ISBN 3-540-44389-4.

[15] Браверман, Марк ; Кун-Ко, Янг; Рубинштейн, Авиад; Вайнштейн, Омри (2017). «Твердость ETH для плотного $k$ -подграфа с идеальной полнотой». В Klein, Филип Н. (ред.). Материалы двадцать восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA 2017, Барселона, Испания, отель Porta Fira, 16-19 января . Общество промышленной и прикладной математики. С. 1326–1341. arXiv : 1504.08352 . DOI : 10.1137 / 1.9781611974782.86 . Руководство по ремонту 3627815 .

[16] Зоопарк сложности : класс QP: квазиполиномиальное время

[ETH-17] Impagliazzo, Рассел ; Патури, Рамамохан (2001). «О сложности k -SAT» (PDF) . Журнал компьютерных и системных наук . 62 (2): 367–375. DOI : 10,1006 / jcss.2000.1727 . Руководство по ремонту 1820597 .

[18] Ааронсон, Скотт (5 апреля 2009 г.). «Не совсем экспоненциальная дилемма» . Штетл-Оптимизированный . Проверено 2 декабря 2009 года .

[19] Зоопарк сложности : класс SUBEXP: детерминированная субэкспоненциально-временная

[20] Мозер, П. (2003). «Категории Бэра по классам малой сложности». В Анджей Лингас; Бенгт Дж. Нильссон (ред.). Основы теории вычислений: 14-й Международный симпозиум, FCT 2003, Мальмё, Швеция, 12-15 августа 2003 г., Труды . Конспект лекций по информатике . 2751 . Берлин, Нью-Йорк: Springer-Verlag. С. 333–342. DOI : 10.1007 / 978-3-540-45077-1_31 . ISBN 978-3-540-40543-6. ISSN 0302-9743 .

[21] Miltersen, РВ (2001). «Дерандомизация классов сложности». Справочник по рандомизированным вычислениям . Комбинаторная оптимизация. Kluwer Academic Pub. 9 : 843. DOI : 10.1007 / 978-1-4615-0013-1_19 . ISBN 978-1-4613-4886-3.

[22] Куперберг, Грег (2005). "Субэкспоненциальный квантовый алгоритм для проблемы диэдральной скрытой подгруппы". SIAM Journal on Computing . Филадельфия. 35 (1): 188. arXiv : Quant-ph / 0302112 . DOI : 10.1137 / s0097539703436345 . ISSN 1095-7111 .

[23] Одед Регев (2004). "Субэкспоненциальный алгоритм времени для задачи о диэдральной скрытой подгруппе с полиномиальным пространством". arXiv : Quant-ph / 0406151v1 .

[24] Grohe, Мартин; Нойен, Даниэль (2021). "Последние достижения в проблеме изоморфизма графов". arXiv : 2011.01366 . Цитировать журнал требует |journal=( помощь )

[25] Флум, Йорг; Grohe, Мартин (2006). Параметризованная теория сложности . Springer. п. 417. ISBN 978-3-540-29952-3.

[26] Impagliazzo, R .; Paturi, R .; Зейн, Ф. (2001). «Какие проблемы имеют сильно экспоненциальную сложность?» . Журнал компьютерных и системных наук . 63 (4): 512–530. DOI : 10,1006 / jcss.2001.1774 .

[27] Майр, Эрнст В .; Мейер, Альберт Р. (1982). «Сложность словесных задач для коммутативных полугрупп и полиномиальных идеалов» . Успехи в математике . 46 (3): 305–329. DOI : 10.1016 / 0001-8708 (82) 90048-2 . Руководство по ремонту 0683204 .

[28] Дэвенпорт, Джеймс Х .; Хайнц, Джоос (1988). «Исключение реального квантора двояко экспоненциально» . Журнал символических вычислений . 5 (1-2): 29–35. DOI : 10.1016 / S0747-7171 (88) 80004-X . Руководство по ремонту 0949111 .

[29] Коллинз, Джордж Э. (1975). «Исключение кванторов для вещественных замкнутых полей цилиндрическим алгебраическим разложением». В Брахаге, Х. (ред.). Теория автоматов и формальных Языки: вторая GI конференция, Кайзерслаутерн, 20-23 мая, 1975 . Конспект лекций по информатике. 33 . Springer. С. 134–183. DOI : 10.1007 / 3-540-07407-4_17 . Руководство по ремонту 0403962 .

[1]