Название для «равномерно полиномиального» подкласса XP?

Предположим, что - параметризованный язык относительно некоторого алфавита . -slice из является , множество экземпляров в , которые имеют параметр . Класс сложности содержит параметризованные языки такие, что для каждого $L$ $\Sigma$ $k$ $L$ $L_k = L \cap \{(x,k) \mid x \in \Sigma^{*}\}$ $L$ $k$ $\mathsf{XP}$ $L$ $L_k \in P$ $k$ возможно, с другим алгоритмом и полиномиальным временем выполнения для каждого . Каждый фиксированного параметр послушный язык в , и существует языки в , которые не являются в ; это предложение 27.1.1 в учебнике Downey & Fellows 2013. $k$ $\mathsf{XP}$ $\mathsf{XP}$ $\mathsf{FPT}$

Однако видимому, имеет нетривиальную структуру за пределами этого, поскольку можно стратифицировать этот класс на основании того, насколько быстро степень ограничивающего полинома растет с : для степень постоянна, тогда как для она может расти произвольно. Downey & Fellows ничего не упоминает о структуре кроме предложения 27.1.1, и обсуждение в учебнике Flum & Grohe 2006 не намного более детально. $\mathsf{XP}$ $k$ $\mathsf{FPT}$ $\mathsf{XP}$ $\mathsf{XP}$

Исходя из моего предыдущего вопроса Пределы вариантов Independent Set? существует ли имя для подкласса в где если существует многочлен такой, что каждый экземпляр в может быть определен не более, чем шагов? $\mathsf{Q}$ $\mathsf{XP}$ $L \in \mathsf{Q}$ $g_L$ $(x,k)$ $L$ $|x|^{g_L(k)}$

Другими словами, этот класс допускает только до время вместо время для некоторой произвольной функции , как и для . $\mathsf{Q}$ $|x|^{\text{poly}(k)}$ $|x|^{g(k)}$ $g$ $\mathsf{XP}$

cc.complexity-theory reference-request parameterized-complexity Андраш Саламон
источник

Это большой вопрос! Я на самом деле очень заинтересован в подклассе, где многочлен является линейным. То есть Q позволяет только до

| x |^{O (k)}

$\vert x \vert ^{O(k)}$

Майкл Вехар

Ответы:

Я не думаю, что этот подкласс был изучен в литературе (и получил название). $\textsf{XP}$

Одна из причин, по которой исследователи могут уклоняться от изучения этого подкласса, заключается в том, что он не закрыт при fpt-сокращениях (и поэтому придется иметь дело с «раздражающим» новым типом сокращений). Это связано с тем, что fpt-reductions позволяет значению параметра увеличиваться сверхполиномиально (если оно ограничено некоторой вычислимой функцией старого значения параметра). Чтобы получить ограниченное представление о fpt-reductions, при которых ваш подкласс закрыт, вам нужно добавить ограничение, что fpt-reductions требует, чтобы новое значение параметра было ограничено некоторым полиномом от старого значения параметра. $\textsf{XP}$

Рональд де Хаан
источник

Сокращения, о которых вы говорите, изучались в контексте kernlizaiton под названием «преобразования полиномиальных параметров», однако они должны выполняться за полиномиальное время.

Даниелло

Я субъективно думаю, что новый тип сокращения может быть хорошим (не очень раздражающим). Я всегда скептически относился к сокращению fpt, позволяющему

быть неограниченным.

g (k)

$g(k)$

Майкл Вехар

Я видел два понятия линейного fpt-сокращения в литературе, которые требуют ограничения

g (k)

$g(k)$

Майкл Вехар