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

Оценка времени, необходимого для запуска алгоритма

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

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

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

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

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

В следующей таблице суммированы некоторые классы часто встречающихся временных сложностей. В таблице 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 big, стандартное использование алгоритмов с логарифмическим временем не зависит от основания логарифма, появляющегося в выражении 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 в словаре может быть выполнен за логарифмическое время: рассмотрим , где обозначает функцию пола . Если --то есть слово w находится точно в середине словаря -- то мы закончили. В противном случае, если --то есть, если слово 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)}$
• Quicksort , , в своей рандомизированной версии имеет время выполнения, которое находится в ожидании на входе худшего случая. Его нерандомизированная версия имеет время выполнения только при учете средней сложности случая. ${\displaystyle O(n\log n)}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(n\log n)}$
• Пирамидальная сортировка , сортировка слиянием , интросортировка , сортировка двоичным деревом, гладкая сортировка , терпеливая сортировка и т. д. в худшем случае ${\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 ^{poly( n )} , где poly( 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 ) = 2O ^{( 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 элементов. Если элементы различны, сортируется только один такой порядок. Bogosort делит наследие с теоремой о бесконечной обезьяне .

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

Говорят, что алгоритм имеет двойное экспоненциальное время, если 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}}}\right)}$

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

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

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

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

Ссылки

1. Sipser, Michael (2006). Введение в теорию вычислений . Курс Technology Inc. ISBN 0-619-21764-2.
2. Мельхорн, Курт ; Нахер, Стефан (1990). «Ограниченные упорядоченные словари за время O (log log N ) и пространство O ( n ) ». Information Processing Letters . 35 (4): 183–189. doi :10.1016/0020-0190(90)90022-P.
3. Тао, Теренс (2010). "1.11 Тест на простоту AKS". Эпсилон комнаты, II: Страницы третьего года математического блога . Аспирантура по математике. Том 117. Провиденс, Род-Айленд: Американское математическое общество. стр. 82–86. doi :10.1090/gsm/117. ISBN 978-0-8218-5280-4. МР  2780010.
4. Lenstra, HW Jr. ; Pomerance, Carl (2019). "Проверка простоты с гауссовыми периодами" (PDF) . Журнал Европейского математического общества . 21 (4): 1229–1269. doi :10.4171/JEMS/861. hdl :21.11116/0000-0005-717D-0. MR  3941463. S2CID  127807021.
5. Calude, Cristian S. и Jain, Sanjay и Khoussainov, Bakhadyr и Li, Wei и Stephan, Frank (2017). «Решение игр на четность за квазиполиномиальное время». Труды 49-го ежегодного симпозиума ACM SIGACT по теории вычислений . Ассоциация вычислительной техники. стр. 252–263. doi : 10.1145/3055399.3055409. hdl : 2292/31757. ISBN 9781450345286. S2CID  30338402.{{cite book}}: CS1 maint: multiple names: authors list (link)
6. Babai, László ; Fortnow, Lance ; Nisan, N. ; Wigderson, Avi (1993). «BPP имеет субэкспоненциальное время моделирования, если EXPTIME не имеет публикуемых доказательств». Computational Complexity . 3 (4). Berlin, New York: Springer-Verlag : 307–318. doi :10.1007/BF01275486. S2CID  14802332.
7. Брэдфорд, Филлип Г.; Роулинс, Грегори Дж. Э.; Шеннон, Грегори Э. (1998). «Эффективное упорядочение цепочек матриц за полилогарифмическое время». SIAM Journal on Computing . 27 (2): 466–490. doi :10.1137/S0097539794270698. MR  1616556.
8. Holm, Jacob; Rotenberg, Eva (2020). «Полностью динамическое тестирование планарности за полилогарифмическое время». В Makarychev, Konstantin; Makarychev, Yury; Tulsiani, Madhur; Kamath, Gautam; Chuzhoy, Julia (ред.). Труды 52-го ежегодного симпозиума ACM SIGACT по теории вычислений, STOC 2020, Чикаго, Иллинойс, США, 22–26 июня 2020 г. Association for Computing Machinery. стр. 167–180. arXiv : 1911.03449 . doi :10.1145/3357713.3384249. ISBN 978-1-4503-6979-4.
9. Кумар, Рави; Рубинфельд, Ронитт (2003). «Сублинейные алгоритмы времени» (PDF) . SIGACT News . 34 (4): 57–67. doi :10.1145/954092.954103. S2CID  65359.
10. Рубинфельд, Ронитт (2019). «Локальные вычислительные алгоритмы». Труды симпозиума ACM 2019 года по принципам распределенных вычислений (PODC) . стр. 3. doi :10.1145/3293611.3331587. ISBN 978-1-4503-6217-7.
11. Наик, Ашиш В.; Реган, Кеннет В.; Сивакумар, Д. (1995). «О теории квазилинейной временной сложности» (PDF) . Теоретическая информатика . 148 (2): 325–349. doi : 10.1016/0304-3975(95)00031-Q . MR  1355592.
12. Седжвик, Роберт; Уэйн, Кевин (2011). Алгоритмы (4-е изд.). Pearson Education. стр. 186.
13. Пападимитриу, Христос Х. (1994). Сложность вычислений . Рединг, Массачусетс: Эддисон-Уэсли. ISBN 0-201-53082-1.
14. Кобэм, Алан (1965). «Внутренняя вычислительная сложность функций». Proc. Логика, методология и философия науки II . Северная Голландия.
15. Braverman, Mark ; Kun-Ko, Young; Rubinstein, Aviad; Weinstein, Omri (2017). "ETH hardness for denset- k -subgraph with perfect completeness". В Klein, Philip N. (ред.). Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Барселона, Испания, Hotel Porta Fira, 16-19 января . Society for Industrial and Applied Mathematics. стр. 1326–1341. arXiv : 1504.08352 . doi :10.1137/1.9781611974782.86. ISBN 978-1-61197-478-2. МР  3627815.
16. Complexity Zoo : Класс QP: Квазиполиномиальное время
17. Импальяццо, Рассел ; Патури, Рамамохан (2001). «О сложности k-SAT» (PDF) . Журнал компьютерных и системных наук . 62 (2): 367–375. doi : 10.1006/jcss.2000.1727 . MR  1820597.
18. Ааронсон, Скотт (5 апреля 2009 г.). «Не совсем экспоненциальная дилемма». Shtetl-Optimized . Получено 2 декабря 2009 г.
19. Complexity Zoo : Класс SUBEXP: Детерминированное субэкспоненциальное время
20. Moser, P. (2003). "Категории Бэра для классов малой сложности". В Andrzej Lingas; Bengt J. Nilsson (ред.). Fundamentals of Computation Theory: 14th International Symposium, FCT 2003, Malmö, Sweden, 12-15 августа 2003 г., Proceedings . Lecture Notes in Computer Science . Vol. 2751. Berlin, New York: Springer-Verlag. pp. 333–342. doi :10.1007/978-3-540-45077-1_31. ISBN 978-3-540-40543-6. ISSN  0302-9743.
21. Miltersen, PB (2001). "Дерандомизация классов сложности". Handbook of Randomized Computing . Combinatorial Optimization. 9. Kluwer Academic Pub: 843. doi :10.1007/978-1-4615-0013-1_19 (неактивен 18 марта 2024 г.). ISBN 978-1-4613-4886-3.{{cite journal}}: CS1 maint: DOI inactive as of March 2024 (link)
22. Куперберг, Грег (2005). «Квантовый алгоритм субэкспоненциального времени для проблемы скрытой подгруппы диэдра». Журнал SIAM по вычислениям . 35 (1). Филадельфия: 188. arXiv : quant-ph/0302112 . doi : 10.1137/s0097539703436345. ISSN  1095-7111. S2CID  15965140.
23. Одед Регев (2004). «Субэкспоненциальный алгоритм времени для задачи о скрытой подгруппе диэдра с полиномиальным пространством». arXiv : quant-ph/0406151v1 .
24. Гроэ, Мартин; Нойен, Даниэль (2021). «Последние достижения в проблеме изоморфизма графов». В Dabrowski, Konrad K.; Gadouleau, Maximilien; Georgiou, Nicholas; Johnson, Matthew; Mertzios, George B.; Paulusma, Daniel (ред.). Surveys in combinatorics 2021 . London Mathematical Society Lecture Note Series. Vol. 470. Cambridge University Press. pp. 187–234. arXiv : 2011.01366 . ISBN 978-1-009-01888-3. МР  4273431.
25. Флум, Йорг; Гроэ, Мартин (2006). Параметризованная теория сложности. Springer. стр. 417. ISBN 978-3-540-29952-3.
26. Импальяццо, Р.; Патури, Р.; Зейн, Ф. (2001). «Какие проблемы имеют строго экспоненциальную сложность?». Журнал компьютерных и системных наук . 63 (4): 512–530. doi : 10.1006/jcss.2001.1774 .
27. Майр, Эрнст В.; Майер , Альберт Р. (1982). «Сложность проблем со словами для коммутативных полугрупп и полиномиальных идеалов». Advances in Mathematics . 46 (3): 305–329. doi : 10.1016/0001-8708(82)90048-2 . MR  0683204.
28. Дэвенпорт, Джеймс Х.; Хайнц , Йос (1988). «Устранение вещественных квантификаторов является дважды экспоненциальным». Журнал символических вычислений . 5 (1–2): 29–35. doi : 10.1016/S0747-7171(88)80004-X . MR  0949111.
29. Коллинз, Джордж Э. (1975). «Устранение квантификаторов для вещественных замкнутых полей с помощью цилиндрической алгебраической декомпозиции». В Brakhage, H. (ред.). Теория автоматов и формальные языки: 2-я конференция GI, Кайзерслаутерн, 20–23 мая 1975 г. Lecture Notes in Computer Science. Vol. 33. Springer. pp. 134–183. doi : 10.1007/3-540-07407-4_17 . ISBN 978-3-540-07407-6. МР  0403962.