Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

содержит несколько сотен задач и продолжает пополняться. Многие вновь ус­ тановленные ТУР-полные задачи печатаются в журнале Journal of Algorithms. В действительности о большей части задач комбинаторной оптимизации известна либо полиномиальная разрешимость, либо ТУР-полнота, что является еш,ё одним подтверждением гипотезы § 6. Класс Е Как уже указано, считается, что алгоритм имеет полиномиальную времен­ ную сложность, если суш,ествует полином р(х) такой, что на любом входном слове длины п алгоритм завершает вычисления после выполнения не более чем р(п) операций. Если такого полинома не суш,ествует, временная сложность считается экспоненциальной. Таким образом, для них число операций возрас­ тает быстрее значений любого полинома. Кроме этого определения, суш,ествует и второе определение: алгоритм имеет экспоненциальную временную сложность, если его временная сложность имеет порядок не меньше, чем ссГ, где с >0, а (а > 1) - постоянные. Другими словами, временная сложность f(n) является экспоненциальной, если суш,ест- вуют постоянные с >О, а >1, такие что C(f <f(n) для всех п, кроме конечного числа значений п. При первом определении, например, задача, имеющая сложность порядка )), будет отнесена к задаче с экспоненциаль­ ной временной сложностью, а по второму определению - нет. Отметим, что функция , хотя и растет быстрее любого полинома, но растёт медленнее, чем, например 2". Большинство экспоненциальных алгоритмов - это просто варианты полно­ го перебора. Экспоненциальные алгоритмы не считаются «хорошими», в отли­ чие от полиномиальных алгоритмов, которые, как уже указывалось, считаются «хорошими». К экспоненциальным задачам относятся задачи, в которых требу­ ется построить множество всех подмножеств данного множества, все полные подграфы некоторого графа или же все поддеревья некоторого графа. Некоторые экспоненциальные алгоритмы весьма хорошо зарекомендовали себя на практике. Дело в том, что временная сложность определяется для худ­ шего случая, а многие задачи могут быть не так плохи. Для решения задачи линейного программирования суш,ествует так назы­ ваемый симплекс-метод (алгоритм), который хотя и экспоненциален в худшем случае, но уверенно работает на практике для задач достаточно большого раз­ мера. Отметим, что для решения задачи линейного программирования Л. Г. Ха- чиян в 1979 г. предложил алгоритм эллипсоидов, который имеет полиномиаль­ ную временную сложность. 230