Nome da subclasse "uniformemente polinomial" do XP?

10

Suponha que é uma linguagem parametrizada em relação a algum alfabeto . A fatia de é , o conjunto de instâncias em que têm o parâmetro . A classe de complexidade contém as linguagens parametrizadas modo que para cada , possivelmente com um algoritmo diferente e tempo de execução polinomial vinculado a cada . Cada idioma tratável de parâmetro fixo está em e há idiomas emLk G G K = G { ( x , k ) | x Σ * } L k X P G G KP k k X P X P F P TΣkLLk=L{(x,k)xΣ}LkXPLLkPkkXPXPque não estão em ; esta é a Proposição 27.1.1 do livro didático de Downey & Fellows 2013.FPT

No entanto, parece ter uma estrutura não trivial além disso, pois é possível estratificar essa classe com base na rapidez com que o grau do polinômio delimitador cresce com : para o grau é constante, enquanto que para pode crescer arbitrariamente. Downey & Fellows não menciona nada sobre a estrutura de além da Proposição 27.1.1, e a discussão no livro didático de Flum & Grohe 2006 não é muito mais detalhada. k F P T X P X PXPkFPTXPXP

Na sequência da minha pergunta anterior Limites de variantes do Independent Set? existe um nome para a subclasse de que se houver um polynomial tal que todas as instâncias em possam ser decididas no máximo etapas?X P L Q g L ( x , k ) L | x | g L ( k )QXPLQgL(x,k)L|x|gL(k)

Em outras palavras, essa classe permite apenas até tempo em vez de tempo para alguma função arbitrária como para .| x | poli ( k ) | x | g ( k ) g X PQ|x|poli(k)|x|g(k)gXP

András Salamon
fonte
Esta é uma grande pergunta! Na verdade, estou muito interessado na subclasse em que o polinômio é linear. Ou seja, Q permite apenas até . |x|O(k)
Michael Wehar

Respostas:

6

Eu não acho que essa subclasse do tenha sido estudada na literatura (e receba um nome).XP

Uma razão pela qual os pesquisadores podem se esquivar de estudar essa subclasse é que ela não é fechada com reduções de fpt (e, portanto, seria preciso lidar com um novo tipo de reduções "irritante"). Isso ocorre porque as reduções de fpt permitem que o valor do parâmetro exploda superpolinomialmente (desde que seja limitado por alguma função computável do antigo valor do parâmetro). Para obter uma noção restrita de reduções de fpt sob a qual sua subclasse do é fechada, você precisará adicionar a restrição de que as reduções de fpt exigem que o novo valor do parâmetro seja limitado por algum polinômio do valor antigo do parâmetro.XP

Ronald de Haan
fonte
11
As reduções de que você fala foram estudadas no contexto de kernlizaiton sob o nome "transformações polinomiais de parâmetros", no entanto, essas precisam ser executadas em tempo polinomial.
Daniello
Subjetivamente, acho que um novo tipo de redução pode ser bom (não muito irritante). Eu sempre fui cético em relação às reduções de fpt, ​​permitindo que fosse ilimitado. g(k)
Michael Wehar
Eu vi duas noções de redução linear de fpt na literatura que exigem que seja delimitado. g(k)
22417 Michael Wehar