Элементарные оценки параметров в трактовке с фиксированными параметрами?

В определении (сильной) управляемости с фиксированными параметрами временная граница является выражением вида где входной экземпляр - с параметром , - многочлен, а - вычислимая функция.

е (К), п (| Икс |),

$f(k).p(|x|),$

(x, k)

$(x,k)$

k

$k$

p

$p$

f

$f$

Можно заменить требование вычислимости для другими классами функций, если понятие редукции ограничено аналогичным образом. (Например, Flum и Grohe охватывают экспоненциальные и субэкспоненциальные семейства в главах 15–16 своего учебника с соответствующими сокращениями erf и serf.) $f$

Кто-нибудь изучал семейство элементарных функций для оценки параметра ? $f$

Элементарная функция может быть ограничена сверху неподвижной башней экспонента, так что этот класс замкнут относительно композиции. Тогда рост параметра в редукции должен быть ограничен сверху еще и элементарной функцией.

Существуют интересные проблемы из теории автоматов, которые можно трактовать с фиксированным параметром, но где граница параметра не элементарна (если P = NP, см. Frick and Grohe, doi: 10.1016 / j.apal.2004.01.007 ). Мне интересно, смотрел ли кто-нибудь на проблемы с фиксированными параметрами, которые исключают фиксированные значения параметра, приводящие к таким «галактическим» постоянным (используя термин Ричарда Липтона и Кена Ригана). Если говорить дико, такое ограничение может иметь полезные связи с теорией конечных моделей, например, характеризоваться фрагментом монадической логики второго порядка, который не приводит к неэлементарным константам, которые могут возникнуть в результате применения теоремы Курселя к фрагменту с неограниченное чередование кванторов.

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

Каков пример «интересных задач из теории автоматов, которые можно трактовать с фиксированными параметрами, но где граница параметров не элементарна».

Суреш Венкат

N P \neq P

$NP\ne P$

Ответы:

В диссертации диссертации " Модифицированные параметры комплексной теории". », Марк Вейер, среди прочего, рассматривал иерархии в FPT с функцией f и сокращениями между ними. Он также действительно связал эти подчиненные иерархии с фрагментами FO и MSO: глава 6 по существу посвящена связи между FO / MSO (количество чередований кванторов в формулах) и функцией f (w) в теореме Курселя (w является ширина дерева). Он рассмотрел как верхнюю, так и нижнюю границы и, используя вышеупомянутую структуру сокращения между определенными иерархиями в рамках FPT, он смог дать довольно жесткие границы. Экзаменаторами диссертации были Флум и Гроэ.

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

Александр Лангер
источник

Спасибо, не думал проверять тезисы. Это выглядит очень актуально для приложений, которые я упомянул. Я, вероятно, что-то упускаю, но кроме краткого упоминания на странице 69, границы элементарных параметров не представляют интереса для Вейера.

Андрас Саламон

Я не совсем уверен, что ты имеешь в виду. В общих рамках он рассматривает произвольные классы «ростовых» функций. Например, сокращения определены для произвольных классов функций «роста» (раздел 3.4, с.22). Классы

E_{t}

$\mathcal E_t$ ,

{Q E}_{t}

$\mathcal{QE}_t$ и

{P E}_{t}

$\mathcal{PE}_t$ (определены на стр. 19 и 20) те функции, которые могут быть ограничены башней экспонент высоты

t

$t$ , (Эти три отличаются тем, что у вас есть в

e x p^{t} (\cdot)

$exp^t(\cdot)$ .) Это то, что вы имеете в виду с привязкой элементарного параметра? Эти классы затем часто используются и играют решающую роль в Главе 6.

Александр Лангер,

Для элементарных оценок достаточно просто рассмотреть объединение всех показательных функций. Об этом упоминает Вейер на странице 69 своего тезиса, но, похоже, этот вопрос не рассматривается дальше.

Андрас Саламон