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

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

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

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

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

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

Постоянное время [ править ]

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

Несмотря на название «постоянное время», время выполнения не обязательно должно быть независимым от размера проблемы, но верхняя граница времени выполнения должна быть ограничена независимо от размера проблемы. Например, задача «обменять значения a и b, если необходимо, чтобы ab » называется постоянным временем, даже если время может зависеть от того, верно ли уже, что ab . Однако существует такая постоянная 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 ) независимо от основания логарифма, появляющегося в выражение Т .

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

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

Пример логарифмического времени дает поиск по словарю. Рассмотрим словарь D, который содержит n статей, отсортированных в алфавитном порядке . Мы предполагаем, что для 1 ≤ kn можно получить доступ к k- й записи словаря за постоянное время. Пусть D ( к ) обозначит эту K -го элемента. В соответствии с этими гипотезами, проверка того, есть ли слово w в словаре, может выполняться за логарифмическое время: рассмотрим, где обозначает нижнюю функцию . Если тогда мы закончили. Иначе, еслипродолжите поиск таким же образом в левой половине словаря, в противном случае продолжите аналогично с правой половиной словаря. Этот алгоритм похож на метод, который часто используется для поиска статьи в бумажном словаре.

Полилогарифмическое время [ править ]

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

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

Сублинейное время [ править ]

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

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

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

Поскольку такой алгоритм должен давать ответ без чтения всего ввода, его особенности сильно зависят от доступа, разрешенного к вводу. Обычно для входа, представленного в виде двоичной строки b 1 , ..., 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 для любогос  > 1.

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

  • Сортировка слиянием на месте , O ( n log 2 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 время , если Т ( п ) = о ( п 2 ).

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

Полиномиальное время [ править ]

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

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

  • Выбор рода алгоритм сортировка по п целых чисел выполняемых операций для некоторой константы А . Таким образом, он работает во времени и представляет собой алгоритм с полиномиальным временем.
  • Все основные арифметические операции (сложение, вычитание, умножение, деление и сравнение) могут быть выполнены за полиномиальное время.
  • Максимальные паросочетания в графах можно найти в полиномиальное время.

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

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

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

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

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

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

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

Классы сложности [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

Отношение к NP-полным задачам [ править ]

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

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

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

Первое определение [ править ]

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

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

Второе определение [ править ]

Некоторые авторы определяют субэкспоненциальное время как время работы в 2 o ( n ) . [17] [22] [23] Это определение допускает большее время работы, чем первое определение субэкспоненциального времени. Примером такого алгоритма субэкспоненциального времени является наиболее известный классический алгоритм для целочисленной факторизации, решето общего числового поля , которое работает примерно во времени , где длина входных данных равна n . Другим примером была проблема изоморфизма графов , которую решал самый известный алгоритм с 1982 по 2016 год . Однако на STOC 2016 был представлен алгоритм квазиполиномиального времени. [24]

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

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

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

Гипотеза экспоненциального времени ( 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 poly ( n ) , где poly ( n ) - некоторый многочлен от n . Более формально алгоритм является экспоненциальным по времени, если T ( n ) ограничено O (2 n k ) для некоторой константы k . Задачи, которые допускают алгоритмы экспоненциального времени на детерминированной машине Тьюринга, образуют класс сложности, известный как EXP .

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

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

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

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

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

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

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

См. Также [ править ]

  • Алгоритмы обмена блоками
  • L-обозначение
  • Космическая сложность

Ссылки [ править ]

  1. ^ a b Сипсер, Майкл (2006). Введение в теорию вычислений . ISBN курса Technology Inc. 0-619-21764-2.
  2. ^ Mehlhorn, Курт; Нахер, Стефан (1990). «Ограниченные упорядоченные словари во времени O (log log N) и O (n) пространстве». Письма об обработке информации . 35 (4): 183–189. DOI : 10.1016 / 0020-0190 (90) 90022-P .
  3. ^ Тао, Теренс (2010). «1.11 Тест на простоту AKS» . Эпсилон комнаты, II: страницы третьего курса математического блога . Аспирантура по математике. 117 . Провиденс, Род-Айленд: Американское математическое общество. С. 82–86. DOI : 10,1090 / г / м2 / 117 . ISBN 978-0-8218-5280-4. Руководство по ремонту  2780010 .
  4. ^ Ленстра младший, HW ; Померанс, Карл (11 декабря 2016 г.). «Проверка на простоту с гауссовскими периодами» (PDF) . Cite journal requires |journal= (help)
  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 . ISSN 1095-7111 . 
  7. ^ Холм, Джейкоб; Ротенберг, Ева (2020). «Полностью динамическое тестирование планарности в полилогарифмическом времени» . STOC 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. ^ Наик, Ашиш В .; Regan, Kenneth W .; Сивакумар, Д. (1995). "О теории сложности квазилинейного времени" (PDF) . Теоретическая информатика . 148 (2): 325–349. DOI : 10.1016 / 0304-3975 (95) 00031-q . Проверено 23 февраля 2015 года .
  10. ^ Седжвик, Р. и Уэйн К. (2011). Алгоритмы, 4-е изд . п. 186. Pearson Education, Inc.
  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. ^ Браверман, Марк; Ко, Ён Кун; Рубинштейн, Авиад; Вайнштейн, Омри (2015), Твердость ETH для плотного k- подграфа с идеальной полнотой , arXiv : 1504.08352 , Bibcode : 2015arXiv150408352B.
  16. ^ Зоопарк сложности : класс QP: квазиполиномиальное время
  17. ^ a b Impagliazzo, R .; Патури, Р. (2001). «О сложности k-SAT». Журнал компьютерных и системных наук . Эльзевир . 62 (2): 367–375. DOI : 10,1006 / jcss.2000.1727 . ISSN 1090-2724 . 
  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 . Cite journal requires |journal= (help)
  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. ^ Майр, Э. & Майер, A .: Сложность проблемы слова для коммутативных полугрупп и полиномиальных идеалов. Adv. по математике. 46 (1982) стр. 305–329
  28. ^ JH Davenport & J. Heintz: Исключение реального квантификатора является дважды экспоненциальным.J. Symbolic Comp. 5 (1988) стр. 29–35.
  29. ^ GE Коллинз: Исключение квантора для реальных замкнутых полей с помощью цилиндрической алгебраической декомпозиции. Proc. 2-й. Теория автоматов конференции GI и формальные языки (конспект лекций Springer по информатике, 33) стр. 134–183