FPT-algorithms and their classification on the base of elasticity.pdf Идея параметризированного подхода к оценке сложности алгоритмов и задач былапредложена в 90-х годах прошлого столетия [1]. За последние два десятилетия эта идеянашла применение в различных областях компьютерных наук, таких, как криптогра-фия, искусственный интеллект, вычислительная биология, теория баз данных [2]. Сутьподхода заключается в рассмотрении так называемых параметризированных задач ипараметризированных алгоритмов.Параметризированная задача П состоит в том, что для заданных языкаL(n) С .* х N, где . - некоторый конечный алфавит и N - множество всех неот-рицательных целых чисел, и пары (I, k) Е .* х N требуется определить, является ли(I, k) элементом L(n). Для алгоритма а, решающего данную задачу, (I,k) называютвходом, I - его основной частью, n = |11 -длиной входа и число k - параметром зада-чи. Алгоритм а называют параметризированным, если его вычислительная сложность,определяемая как количество времени исполнения, оценивается с точки зрения длинывхода n и значения параметра k. Таким образом, функция вычислительной сложностипараметризированного алгоритма есть некоторая функция двух переменных t(n, k).Параметризированная задача П считается разрешимой с фиксированным парамет-ром, или FPT-разрешимой (Fixed-Parameter Tractable), если она может быть решенанекоторым параметризированным алгоритмом за время t(n, k) = O(nO(1) /(k)) дляфункции /, зависящей только от параметра k. Класс всех разрешимых с фиксиро-ванным параметром задач обозначается FPT. Соответствующие параметризирован-ные алгоритмы, решающие такие задачи, называют FPT-алгоритмами. Очевидно, чтов FPT лежат все полиномиально разрешимые задачи. Однако наибольший интереспредставляют FPT-разрешимые задачи, являющиеся NP-трудными. С теоретическойточки зрения все эти задачи могут быть решены за полиномиальное время при каждомфиксированном значении параметра. Уже имеются сборники параметризированныхзадач, включая FPT-разрешимые задачи [3].Теория параметризированной сложности развивается по нескольким направлени-ям: определение иерархии классов сложности параметризированных задач, установле-ние условий FPT-разрешимости, выявление взаимосвязи между параметризированнойсложностью и классами приближенных алгоритмов, развитие методов анализа и раз-работки параметризированных алгоритмов. В многочисленных работах по парамет-ризированной теории сложности для анализа и сравнения алгоритмов применяютсяметоды классической (одномерной) теории сложности [4]. Между тем классическая од-номерность ограничивает глубину анализа параметризированных алгоритмов, для ко-торых вычислительная сложность описывается функцией от двух переменных t(n, k).В настоящей работе предлагается мера вычислительной сложности алгоритма, с помо-щью которой можно исследовать темп роста функций многих переменных, анализиро-вать степень влияния структуры входных данных параметризированного алгоритмана его вычислительную сложность, сравнивать между собой FPT-алгоритмы. Этоймерой является частная эластичность. Представленные результаты являются обоб-щением и расширением результатов автора, опубликованных в [5-7] применительнок одномерной теории сложности вычислений.Под частной эластичностью Ex(z) функции z = z(x,y) по аргументу x понимаетсяэластичность переменной z, которая рассматривается как функция только от x и припостоянных значениях у. Частная эластичность Ex(z) связана с частной производнойфункции z = z(x,y) по x соотношением Ex(z) = zj x/z. Аналогично Ey(z) = z^ y/z.В общем случае Ex(z), Ey(z) являются функциями, зависящими от двух аргумен-тов x и y. Однако ситуация упрощается, если учесть тот факт, что для большинствапараметризированных алгоритмов время выполнения алгоритма описывается функ-цией вида z(x,y) = q(x)f(у), где q(x) -количественная компонента, а f(у) -пара-метрическая компонента этой функции. Для такой формы представления функцииz = z(x,y) частные эластичности Ex(z), Ey(z) вырождаются в обычные эластичностифункции одного аргумента: Ex(z) = Ex(q(x)), Ey(z) = Ey (f (y)). Теперь Ex(z) зависитлишь от x, а Ey(z) -от y. Каждая из функций q(x), f (y) принадлежит одному слож-ностному классу множества K = {SUBPOLY, POLY, SUBEXP, EXP, HYPEREXP} поподобающему аргументу [5]. Обозначим через Fx класс сложности функции z(x,y) поаргументу x, а через Fy - класс сложности по аргументу y. Тогда всякому парамет-ризированному алгоритму с функцией вычислительной сложности z(x,y) = q(x)f (y)соответствует пара (Fx, Fy) Е K х K, характеризующая сложность данного алгорит-ма как по длине входа x, так и значению параметра y. Таким образом, мы прихо-дим к двумерной классификации параметризированных алгоритмов. При двумерномподходе более отчетливую и общую формулировку получает определение FPT-алго-ритма: параметризированный алгоритм называется FPT-алгоритмом, если его вычис-лительная сложность задается функцией z(x,y) = q(x)f(y), для которой (Fx, Fy) ЕЕ {SUBPOLY, POLY} х K.Введенная двумерная классификация FPT-алгоритмов не противоречит понятиям,используемым в настоящеевремя в параметризированной теории сложности примени-тельно к FPT-алгоритмам, а лишь формально их уточняет и расширяет. Допустимодальнейшее развитие предложенного подхода в части увеличения числа параметров ианализа других форм представления функций сложности.Подробное изложение представленных результатов можно найти в [8].

Скачать электронную версию публикации