Что является мотивацией для определения управляемости с фиксированными параметрами?

FPT содержит задачи с фиксированными параметрами, которые можно решить за время для некоторой вычислимой функции . Как правило, эта функция рассматривается как единая экспонента, такая как но определение допускает функции, которые растут еще быстрее. Это важно для большой части ранней истории этого класса. Важнейшей частью определения является исключение функций вида , таких как . $f(k)\cdot|x|^{O(1)}$ $f$ $2^{O(k)}$ $f(n,k)$ $n^k$

Вопрос : Какова мотивация этого определения?

Что меня озадачивает, так это то, что если фиксировано (согласно «трактуемости с фиксированными параметрами»), то является полиномом от . Итак, почему так важно исключить ? $k$ $n^k$ $n$ $n^k$

cc.complexity-theory fixed-parameter-tractable Дуглас С. Стоунс
источник

Потому что часто является тривиальным с точки зрения теории и слишком медленным с практической точки зрения. Один из способов выразить это в том, что бизнес FPT пытается понять вычислительную сложность задач для значений параметров, которые находятся в приблизительном диапазоне и .

n^{k}

$n^k$

n \approx 1000000

$n ≈ 1000000$

k \approx 30

$k ≈ 30$

Юкка Суомела

Хм ... так что, если я правильно понимаю, если мы пустим в FPT, то в конечном итоге мы включим кучу проблем с решением тривиально, с помощью алгоритмов грубой силы.

n^{k}

$n^k$

Дуглас С. Стоунс

Вот так. Конечно, существует иерархия проблем с фиксированными параметрами, и FPT находится внизу. п ^ к находится на вершине. В более общем смысле, идея состоит в том, чтобы попытаться отделить влияние параметра и влияние , а следовательно, и две отдельные части времени выполнения.

n

$n$

Суреш Венкат

@JukkaSuomela: Я думаю, что ваш комментарий может быть ответом.

Суреш Венкат

Ответы:

Если вам требуется только, чтобы скорость роста была полиномом от для фиксированного , тогда вы получите определение параметризованного класса сложности XP, который, безусловно, представляет интерес, поэтому нет ничего плохого в его рассмотрении. $n$ $k$

Вы получите определение FPT, если дополнительно наложите условие, что степень многочлена от остается фиксированной при увеличении параметра. FPT оказывается особенно доступным подклассом XP, и интуитивно, причина в том, что выражение, такое как , не взрывается так быстро, как выражение, такое как , если и являются как $n$ $2^k n^2$ $k^2 n^k$ $k$ $n$ растет. Эта интуиция поддерживается как на практике, так и в теории; проблемы FPT имеют тенденцию быть заметно более практичными, чем произвольные проблемы XP, и можно также получить хорошую теоретическую картину структуры XP, начав с FPT внизу и построив иерархии других подклассов XP (таких как Ж иерархия) над ним.

Тимоти Чоу
источник