Самостоятельная работа №1 По предмету: Алгоритмы проектирования Статические и динамические меры сложности алгоритма

БППвероятностная машина Тьюринга за полиномиальное время.

БКП: класс сложности решаемых задач с двоичными ошибками на квантовой машине Тьюринга за полиномиальное время.

P — наименьший класс временной сложности в детерминированной машине, то есть с точки зрения изменения устойчивой модели машины. (Например, переход от однопоточной машины Тьюринга к многопоточной машине Тьюринга может привести к квадратичному ускорению, но любой алгоритм, работающий за полиномиальное время в одной модели, будет выполняться за полиномиальное время в другой.)
Суперполиномиальное время
Говорят, что алгоритм работает за суперполиномиальное время, если T(n) не ограничено указанным выше полиномом. Это время равно ω ( nc) для всех констант c, где n — входной параметр, обычно количество входных битов.
Например, алгоритм, реализующий число 2, выполняет n шагов за суперполиномиальное время (точнее, за экспоненциальное время), чтобы вставить размер n.
Алгоритм, который использует ресурсы указателя, очевидно, является суперполиномиальным, но некоторые алгоритмы очень слабо суперполиномиальны.Например, тест простоты Адлемана-Померанса-Румели * выполняется за время n O (log log n) на n-битном входе.Он большой достаточно l растет быстрее, чем любой многочлен n, но размер входных данных должен быть достаточно большим, чтобы над ним не доминировал полином малой степени.
Алгоритм с суперполиномиальным временем находится вне класса сложности. Тезис Кобэма утверждает, что эти алгоритмы непрактичны, и во многих случаях так и есть. Поскольку проблема равенства классов P и NP не решена, в настоящее время не известны алгоритмы решения NP-полных задач за полиномиальное время.
Квазиполиномиальное время
Алгоритмы с квазиполиномиальным временем. Эти алгоритмы работают медленнее, чем алгоритмы с полиномиальным временем, но не так медленно, как алгоритмы с экспоненциальным временем. Наихудшее время выполнения для квазиполиномиального алгоритма равно c . Известный классический алгоритм разложения целого числа на множители не является квазиполиномиальным, так как время выполнения нельзя выразить как 2 O ((log ⁡ n) c) (\ displaystyle 2 ^ (O ((\log n) ^ (c)))) для некоторой константы c... Если константа "c" в определении алгоритма квазиполиномиального времени равна 1, то алгоритм с полиномиальным временем, 1 меньше , мы получаем алгоритм с меньшим линейным временем.
Алгоритмы квазиполиномиального времени обычно возникают при сведении NP-сложной задачи к другой задаче. Например, вы можете взять NP-сложную задачу, скажем, 3SAT, и свести ее к другой задаче B, но размер задачи увеличится. 2 O ((log ⁡ n) c) (\ displaystyle 2 ^ (O ((\ log n) ^ (c))))... В этом случае сведение не доказывает, что задача B является NP-трудной; такая редукция показывает, что полиномиального алгоритма для B нет, только если нет квазиполиномиального алгоритма для 3SAT (и затем для всех задач). Точно так же есть некоторые задачи, для которых мы знаем алгоритмы квазиполиномиального времени, но для которых алгоритмы полиномиального времени неизвестны.Такие проблемы возникают в приближенных алгоритмах. Известным примером является направленная задача Штейнера, для которой существует приближенный квазиполиномиальный алгоритм с коэффициентом сходимости. O (log 3 ⁡ n) (\ displaystyle O (\ log ^ (3) n)) (где n — количество вершин), но существование алгоритма с полиномиальным временем — открытая проблема.
Класс сложности состоит из всех задач, связанных с алгоритмами квазиполиномиального времени QP. Его можно определить с точки зрения DTIME следующим образом.
КП =⋃сеN DTIME(2(log⁡n)c)(\displaystyle(\mbox(QP))=\bigcup_(c\in\mathbb(N))(\mbox(DTIME))(2^((\log n )^(с))))