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

Связь с NP-полными задачами
В теории сложности нерешенная проблема равенства между классами P и NP спрашивает, существуют ли алгоритмы для решения всех проблем в классе NP за полиномиальное время. Все известные алгоритмы для NP-полных задач, таких как 3SAT, имеют экспоненциальное время. Более того, существует гипотеза, что не существует алгоритмов с субэкспоненциальным временем выполнения для большинства естественных NP-полных задач. Здесь "субэкспоненциальное время" - это второе определение ниже (С другой стороны, многие задачи теории графов, естественно представленные матрицами смежности, могут быть решены за субэкспоненциальное время, потому что размер входных данных равен квадрату числа вершин.) Эта гипотеза (для проблемы k-SAT) известна как гипотеза экспоненциального времени... NP-to'
Субэкспоненциальное время
Термин субэкспоненциальное время используется для выражения того, что время выполнения некоторых алгоритмов может расти быстрее, чем любой полином, но остается значительно меньше экспоненциального В этом смысле задачи с субэкспоненциальными алгоритмами времени являются только экспоненциальными, более гибкими, чем временные алгоритмы. Точное определение «субэкспоненциального» еще не общепринято, и ниже мы представляем два наиболее распространенных определения.
Первое определение
Если задача решается алгоритмом, логарифм времени работы которого растет меньше любого заданного полинома, говорят, что задача решается за субэкспоненциальное время. Точнее, если существует алгоритм, решающий задачу за время O(2ne) для любого e > 0, то задача имеет субэкспоненциальное время Все такие задачи образуют класс сложности SUBEXP, который можно выразить через DTIME.
СУБЭКСП =⋂e>0 DTIME(2 ne)(\displaystyle(\text(SUBEXP))=\bigcap_(\varepsilon>0)(\text(DTIME))\left(2^(n^(\varepsilon) ))) \ верно))
Обратите внимание, что здесь e не является частью входных данных и для каждого e может существовать уникальный алгоритм решения задачи.
Второе определение
Некоторые авторы определяют субэкспоненциальное время как время работы 2 o ( n ). Это определение позволяет работать дольше, чем первое определение.Примером такого алгоритма субэкспоненциального времени является известный классический алгоритм разложения целых чисел на множители, метод решета поля сумм, который занимает около 100 раз. 2 O ~ (n 1/3) (\displaystyle 2 ^ ((\тильда (O)) (n ^ (1/3))), где длина входных данных равна n . Другой пример, знаменитый алгоритм Проблемы изоморфизма графов, время выполнения которых 2 O ((n log ⁡ n)) (\ displaystyle 2 ^ (O ((\ sqrt (()) n \ log n)))).
Обратите внимание, что этот алгоритм отличается тем, является ли он субэкспоненциальным по количеству вершин или по количеству ребер. V параметризованная сложность четко выражается указанием разностной пары, задачи решения и параметра k. SUBEPT — это класс всех параметризованных задач, которые выполняются за субэкспоненциальное время от k и для полинома n:
SUBEPT = DTIME (2 o (k)⋅поли(н)). (\displaystyle (\text(SUBEPT)) = (\text(DTIME))\left(2^(o(k))\cdot(\text(poly))(n)\right).)
Точнее, SUBEPT — это класс всех параметризованных функций (L, k) (\displaystyle (L,k)), для которых существует вычислительная функция f: N → N (\displaystyle f:\mathbb(N)\to\ mathbb(N)) С fео (к) (\ Displaystyle е \ в о (к))и алгоритм решения L в течение 2 f (k)⋅поли (п) (\ Displaystyle 2 ^ (е (к)) \ cdot (\ текст (поли)) (п)).