Limites elementares no parâmetro na rastreabilidade de parâmetro fixo?

Na definição de tratabilidade de parâmetro fixo (forte), o tempo limite é uma expressão da forma onde a instância de entrada é com o parâmetro , é um polinômio é uma função computável .

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

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

(x, k)

$(x,k)$

k

$k$

p

$p$

f

$f$

É possível substituir o requisito de computabilidade para por outras classes de funções, desde que a noção de redução seja igualmente restrita. (Por exemplo, Flum e Grohe cobrem famílias exponenciais e subexponenciais nos capítulos 15–16 do livro, com as reduções associadas a erf e servf.) $f$

Alguém já estudou a família de funções elementares para o parâmetro vinculado ? $f$

Uma função elementar pode ser delimitada acima por uma torre fixa de exponenciais, portanto essa classe é fechada sob composição. O crescimento do parâmetro em uma redução também deve ser limitado acima por uma função elementar.

Existem problemas interessantes na teoria dos autômatos que são tratáveis por parâmetros fixos, mas onde o limite de parâmetros não é elementar (a menos que P = NP, veja Frick e Grohe, doi: 10.1016 / j.apal.2004.01.007 ). Pergunto-me se alguém examinou os problemas tratáveis de parâmetros fixos que excluem valores fixos do parâmetro que leva a essas constantes "galácticas" (para usar o termo de Richard Lipton e Ken Regan). Especulando descontroladamente, essa restrição pode ter conexões úteis com a teoria finita dos modelos, como ser caracterizada por um fragmento da lógica monádica de segunda ordem que não leva a constantes não elementares que podem surgir da aplicação do Teorema de Courcelle a um fragmento com alternância ilimitada do quantificador.

cc.complexity-theory reference-request fixed-parameter-tractable András Salamon
fonte

O que é um exemplo de "problemas interessantes da teoria dos autômatos que são tratáveis por parâmetros fixos, mas onde o parâmetro vinculado é não elementar".

Suresh Venkat

@SureshVenkat Acredito que seja o problema de verificação de modelo da fórmula FO e MSO em árvores, parametrizado pelo comprimento da fórmula. Os limites inferiores para FO e MSO estão sob alguma suposição razoável em complexidade parametrizada e

respectivamente.

N P \neq P

$NP\ne P$

Regularidade

Respostas:

Em sua tese de dissertação " Modi ﬁ zierte parametrische Komplexitatstheorie ", Mark Weyer considerou, entre outras coisas, hierarquias no FPT, que classificaram a função f e reduções entre elas. Ele também relacionou essas sub-hierarquias a fragmentos de FO e MSO: o capítulo 6 é essencialmente sobre a relação entre FO / MSO (o número de alternâncias quantificadoras das fórmulas) e a função f (w) no teorema de Courcelle (w sendo a largura da árvore). Ele considerou os limites superior e inferior e, usando a estrutura de redução acima mencionada entre certas hierarquias dentro do FPT, conseguiu estabelecer limites bastante rígidos. Os examinadores da tese foram Flum e Grohe.

Infelizmente, a tese está em alemão e não sei se o material da tese foi publicado em uma revista em inglês. Estou, portanto, ciente de que eles podem ser de uso limitado para você, mas, mesmo assim, as referências podem ser um bom ponto de partida.

Alexander Langer
fonte

Obrigado, não tinha pensado em verificar teses. Isso parece altamente relevante para os aplicativos que mencionei. Provavelmente estou perdendo alguma coisa, mas, além de uma breve menção na página 69, os limites elementares dos parâmetros não parecem ser do interesse de Weyer.

András Salamon

E_{t}

$\mathcal E_t$

{Q E}_{t}

$\mathcal{QE}_t$

{P E}_{t}

$\mathcal{PE}_t$

t

$t$

e x p^{t} (\cdot)

$exp^t(\cdot)$

Alexander Langer

Para limites elementares, basta considerar a união de todas as funções exponenciais. Isso é mencionado por Weyer na página 69 de sua tese, mas a questão não parece mais ser tratada.

András Salamon