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

Оценка времени, затраченного на запуск алгоритма

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Говорят, что алгоритм работает за полилогарифмическое время , если его время соответствует некоторой константе k . Другой способ написать это . ${\displaystyle T(n)}$ ${\displaystyle O{\bigl (}(\log n)^{k}{\bigr )}}$ ${\displaystyle O(\log ^{k}n)}$

Например, упорядочение цепочки матриц может быть решено за полилогарифмическое время на параллельной машине с произвольным доступом ^[7] , и граф может быть определен как планарный полностью динамическим способом во времени для каждой операции вставки/удаления. ^[8] ${\displaystyle O(\log ^{3}n)}$

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

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

Конкретный термин «алгоритм сублинейного времени» обычно относится к рандомизированным алгоритмам, которые отбирают небольшую часть входных данных и эффективно обрабатывают их, чтобы приблизительно определить свойства всего экземпляра. ^[9] Этот тип алгоритма сублинейного времени тесно связан с тестированием свойств и статистикой .

Другие настройки, при которых алгоритмы могут работать в сублинейном времени, включают:

• Параллельные алгоритмы , которые имеют линейную или большую общую работу (что позволяет им читать весь ввод), но сублинейную глубину .
• Алгоритмы, которые имеют гарантированные предположения о структуре входных данных. Важным примером являются операции со структурами данных , например двоичный поиск в отсортированном массиве.
• Алгоритмы, которые ищут локальную структуру на входе, например, находят локальный минимум в одномерном массиве (можно решить во  времени, используя вариант двоичного поиска). Близким понятием является понятие «алгоритмы локальных вычислений» (LCA), где алгоритм получает большие входные данные и запрашивает локальную информацию о некоторых допустимых больших выходных данных. ^[10] ${\displaystyle O(\log(n))}$

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

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

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

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

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

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

• Сортировка слиянием на месте , ${\displaystyle O(n\log ^{2}n)}$
• Быстрая сортировка , в своей рандомизированной версии, имеет ожидаемое время выполнения для входных данных в худшем случае. Его нерандомизированная версия имеет время работы только с учетом средней сложности случая. ${\displaystyle O(n\log n)}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(n\log n)}$
• Heapsort , сортировка слиянием , интросорт , сортировка двоичного дерева, гладкая сортировка , терпеливная сортировка и т. д. в худшем случае ${\displaystyle O(n\log n)}$
• Быстрое преобразование Фурье , ${\displaystyle O(n\log n)}$
• Расчет массива Монге , ${\displaystyle O(n\log n)}$

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

Сортировки сравнения требуют, по крайней мере, сравнений в худшем случае, потому что , согласно приближению Стирлинга , . Они также часто возникают из рекуррентного соотношения . ${\displaystyle \Omega (n\log n)}$ ${\displaystyle \log(n!)=\Theta (n\log n)}$ ${\textstyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}$

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

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

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

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

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

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

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

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

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

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

• 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-полные задачи суперполиномиального времени.

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

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

Есть некоторые задачи, для решения которых мы знаем алгоритмы с квазиполиномиальным временем, но алгоритм с полиномиальным временем неизвестен. Такие проблемы возникают в алгоритмах аппроксимации; Известным примером является направленная задача о дереве Штейнера , для которой существует алгоритм аппроксимации с квазиполиномиальным временем, достигающий коэффициента аппроксимации ( n — количество вершин), но показать существование такого алгоритма с полиномиальным временем — открытая проблема. ${\displaystyle O(\log ^{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 следующим образом. ^{[6] [19] [20] [21]}

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

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

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

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

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

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

Точнее, SUBEPT — это класс всех параметризованных задач , для которых есть вычислимая функция и алгоритм, решающий L за время . ${\displaystyle (L,k)}$ ${\displaystyle f:\mathbb {N} \to \mathbb {N} }$ ${\displaystyle f\in o(k)}$ ${\displaystyle 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 . ^[26] Гипотеза экспоненциального времени подразумевает, что P ≠ NP .

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

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

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

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

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

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

Алгоритм называется факториальным по времени , если T(n) ограничен сверху факториальной функцией n! . Факториальное время является подмножеством экспоненциального времени (EXP), поскольку для всех . Однако это не подмножество E. ${\displaystyle n!\leq n^{n}=2^{n\log n}=O\left(2^{n^{1+\epsilon }}\right)}$ ${\displaystyle \epsilon >0}$

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

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

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

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

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

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

Смотрите также

• L-обозначение
• Пространственная сложность

Рекомендации

1. Сипсер, Майкл (2006). Введение в теорию вычислений . Курс Technology Inc. ISBN 0-619-21764-2.
2. Мельхорн, Курт ; Нахер, Стефан (1990). «Ограниченные упорядоченные словари во времени O (log log N ) и пространстве O ( n ) ». Письма об обработке информации . 35 (4): 183–189. дои : 10.1016/0020-0190(90)90022-П.
3. Тао, Теренс (2010). «1.11 Тест на простоту АКС». Эпсилон комнаты, II: Страницы третьего года математического блога . Аспирантура по математике. Том. 117. Провиденс, Род-Айленд: Американское математическое общество. стр. 82–86. дои : 10.1090/gsm/117. ISBN 978-0-8218-5280-4. МР  2780010.
4. Ленстра, HW младший ; Померанс, Карл (2019). «Тестирование простоты с гауссовскими периодами» (PDF) . Журнал Европейского математического общества . 21 (4): 1229–1269. дои : 10.4171/JEMS/861. МР  3941463. S2CID  127807021.
5. Калуд, Кристиан С. и Джайн, Санджай и Хусаинов, Бахадыр и Ли, Вэй и Стефан, Фрэнк (2017). «Определение игр на четность за квазиполиномиальное время». Материалы 49-го ежегодного симпозиума ACM SIGACT по теории вычислений . Ассоциация вычислительной техники. стр. 252–263. дои : 10.1145/3055399.3055409. ISBN 9781450345286. S2CID  30338402.{{cite book}}: CS1 maint: date and year (link) CS1 maint: multiple names: authors list (link)
6. Бабай, Ласло ; На данный момент, Лэнс ; Нисан, Н. ; Вигдерсон, Ави (1993). «BPP использует субэкспоненциальное моделирование времени, если у EXPTIME нет опубликованных доказательств». Вычислительная сложность . Берлин, Нью-Йорк: Springer-Verlag . 3 (4): 307–318. дои : 10.1007/BF01275486. S2CID  14802332.
7. Брэдфорд, Филипп Г.; Роулинз, Грегори Дж. Э.; Шеннон, Грегори Э. (1998). «Эффективное упорядочение матричных цепочек за полилогарифмическое время». SIAM Journal по вычислительной технике . 27 (2): 466–490. дои : 10.1137/S0097539794270698. МР  1616556.
8. Холм, Джейкоб; Ротенберг, Ева (2020). «Полностью динамическое тестирование планарности за полилогарифмическое время». У Макарычева Константина; Макарычев Юрий; Тулсиани, Мадхур; Камат, Гаутама; Чужой, Юлия (ред.). Материалы 52-го ежегодного симпозиума ACM SIGACT по теории вычислений, STOC 2020, Чикаго, Иллинойс, США, 22-26 июня 2020 г. Ассоциация вычислительной техники. стр. 167–180. arXiv : 1911.03449 . дои : 10.1145/3357713.3384249.
9. Кумар, Рави; Рубинфельд, Ронитт (2003). «Алгоритмы сублинейного времени» (PDF) . Новости СИГАКТ . 34 (4): 57–67. дои : 10.1145/954092.954103. S2CID  65359.
10. Рубинфельд, Ронитт (2019). «Алгоритмы локальных вычислений». Материалы симпозиума ACM по принципам распределенных вычислений (PODC) 2019 года . п. 3. дои : 10.1145/3293611.3331587.
11. Наик, Ашиш В.; Риган, Кеннет В.; Сивакумар, Д. (1995). «О теории сложности с квазилинейным временем» (PDF) . Теоретическая информатика . 148 (2): 325–349. дои : 10.1016/0304-3975(95)00031-Q . МР  1355592.
12. Седжвик, Роберт; Уэйн, Кевин (2011). Алгоритмы (4-е изд.). Пирсон Образование. п. 186.
13. Пападимитриу, Христос Х. (1994). Вычислительная сложность . Ридинг, Массачусетс: Аддисон-Уэсли. ISBN 0-201-53082-1.
14. Кобэм, Алан (1965). «Внутренняя вычислительная сложность функций». Учеб. Логика, методология и философия науки II . Северная Голландия.
15. Браверман, Марк ; Кун-Ко, Янг; Рубинштейн, Авиад; Вайнштейн, Омри (2017). «Трудность ETH для плотнейшего k -подграфа с идеальной полнотой». Кляйн, Филип Н. (ред.). Материалы двадцать восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA 2017, Барселона, Испания, отель Porta Fira, 16-19 января . Общество промышленной и прикладной математики. стр. 1326–1341. arXiv : 1504.08352 . дои : 10.1137/1.9781611974782.86. МР  3627815.
16. Зоопарк сложности : Класс QP: Квазиполиномиальное время
17. Импальяццо, Рассел ; Патури, Рамамохан (2001). «О сложности k-SAT» (PDF) . Журнал компьютерных и системных наук . 62 (2): 367–375. дои : 10.1006/jcss.2000.1727 . МР  1820597.
18. Ааронсон, Скотт (5 апреля 2009 г.). «Не совсем экспоненциальная дилемма». Shtetl-Оптимизированный . Проверено 2 декабря 2009 г.
19. Зоопарк сложности : Класс SUBEXP: Детерминированное субэкспоненциальное время
20. Мозер, П. (2003). «Категории Бэра на классах малой сложности». В Анджее Лингасе; Бенгт Дж. Нильссон (ред.). Основы теории вычислений: 14-й международный симпозиум, FCT 2003, Мальмё, Швеция, 12–15 августа 2003 г., Труды . Конспекты лекций по информатике . Том. 2751. Берлин, Нью-Йорк: Springer-Verlag. стр. 333–342. дои : 10.1007/978-3-540-45077-1_31. ISBN 978-3-540-40543-6. ISSN  0302-9743.
21. Милтерсен, ПБ (2001). «Дерандомизация классов сложности». Справочник по рандомизированным вычислениям . Комбинаторная оптимизация. Академический паб Клювер. 9 : 843. дои : 10.1007/978-1-4615-0013-1_19. ISBN 978-1-4613-4886-3.
22. Куперберг, Грег (2005). «Квантовый алгоритм субэкспоненциального времени для решения проблемы скрытых диэдральных подгрупп». SIAM Journal по вычислительной технике . Филадельфия. 35 (1): 188. arXiv : quant-ph/0302112 . дои : 10.1137/s0097539703436345. ISSN  1095-7111. S2CID  15965140.
23. Одед Регев (2004). «Алгоритм субэкспоненциального времени для решения задачи о скрытых подгруппах диэдра с полиномиальным пространством». arXiv : Quant-ph/0406151v1 .
24. Гроэ, Мартин; Нойен, Даниэль (2021). «Последние достижения в проблеме изоморфизма графов». arXiv : 2011.01366 . {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
25. Флум, Йорг; Гроэ, Мартин (2006). Параметризованная теория сложности. Спрингер. п. 417. ИСБН 978-3-540-29952-3.
26. Импальяццо, Р .; Патури, Р.; Зейн, Ф. (2001). «Какие задачи имеют сильно экспоненциальную сложность?». Журнал компьютерных и системных наук . 63 (4): 512–530. дои : 10.1006/jcss.2001.1774 .
27. Майр, Эрнст В .; Мейер, Альберт Р. (1982). «Сложность словесных задач для коммутативных полугрупп и полиномиальных идеалов». Достижения в математике . 46 (3): 305–329. дои : 10.1016/0001-8708(82)90048-2 . МР  0683204.
28. Давенпорт, Джеймс Х .; Хайнц, Йоос (1988). «Реальное устранение кванторов является вдвойне экспоненциальным». Журнал символических вычислений . 5 (1–2): 29–35. дои : 10.1016/S0747-7171(88)80004-X . МР  0949111.
29. Коллинз, Джордж Э. (1975). «Устранение кванторов для вещественных замкнутых полей путем цилиндрического алгебраического разложения». В Брэкедже, Х. (ред.). Теория автоматов и формальные языки: 2-я конференция GI, Кайзерслаутерн, 20–23 мая 1975 г. Конспекты лекций по информатике. Том. 33. Спрингер. стр. 134–183. дои : 10.1007/3-540-07407-4_17 . МР  0403962.