Математическая логика и теория алгоритмов

экспоненциальной, если существуют постоянные с >0, а >1, что са" < f{n) для всех, кроме конечного числа значений п. При первом определении, например, задача, имеющая слож­ ность порядка будет отнесена к задаче с экспоненциальной временной сложностью, а по второму определению - нет. Отметим, что функция хотя и растет быст­ рее любого полинома, но растет медленнее, чем, например 2", Большинство экспоненциальных алгоритмов - это просто вари­ анты полного перебора. Экспоненциальные алгоритмы не считаются «хорошими», в отличие от полиномиальных алгоритмов, которые, как уже указывалось, считаются «хорошими». К экспоненциальным зада­ чам относятся задачи, в которых требуется построить множество всех подмножеств данного множества, все полные подграфы некоторого графа или же все поддеревья некоторого графа. Некоторые экспоненциальные алгоритмы весьма хорошо зарекомендовали себя на практике. Дело в том, что временная слож­ ность определяется для худшего случая, а многие задачи могут быть не так плохи. Для решения задачи линейного программирования существует так называемый симплекс-метод (алгоритм), KOTopbnd хотя и экспоненциален в худшем случае - уверенно работает fja практике для задач достаточно большого размера. Отметим, что для решения задачи линейного программирования Л. Г. Хачиян в 1979 г. предло­ жил алгоритм эллипсоидов, который имеет полиномиальную времен­ ную сложность. Метод ветвей и границ успешно решает задачу о рюкзаке, хотя этот алгоритм имеет экспоненциальную временную сложность. Примеров экспоненциальных алгоритмов, успешно используе­ мых на практике, MajM. Более того, даже для полиномиальных алго­ ритмов представляют практический интерес алгоритмы, сложность которых имеет порядок п или Ясно, что алгоритмы со сложностью порядка и'®® вряд ли будут практически используемы. 291