Alguém pode me explicar o que são os kernels (problemáticos) e qual a utilidade deles? Meus slides dizem:
O kernel de um problema parametrizado eueu é uma transformação ( x , k ) ↦ (x′,k′)(x,k)↦(x′,k′) de tal modo que:
( x , k ) ∈ L ⇔ (x′,k′) ∈ L(x,k)∈eu⇔(x′,k′)∈eu
|x′| ≤f( K )|x′|≤f(k) para alguma função gg
transformação deve ser calculada em tempo polinomial.
Como isso está relacionado a um problema que está sendo corrigido nos parâmetros tratáveis?
O que torna os kernels úteis?
De onde vem essa definição.
O exemplo nos meus slides é para cobertura de vértice, mas eu realmente não entendo, porque os slides são meio curtos.
Parece ser sobre uma família de algoritmos, mas não consigo adivinhar qual. Você poderia dar algum contexto.
Este é um conceito bastante padrão (se não básico) na teoria da complexidade. Essas são as coisas que seu professor deveria ter lhe contado, mas também há muito material na Web, sem mencionar os livros. Para onde você olhou? Você já executou uma pesquisa simples? (cc @babou)
@Raphael Como é que uma pergunta sobre NP recebe 80 votos positivos e você acha que a complexidade da kernelização é muito padrão (se não básica) para este site? Se o professor deveria ter dito isso, podemos assumir que ele também explique P, NP, NP-Complete e NP-Hard?
Intuitivamente, um algoritmo de kernelização é um algoritmo que, em tempo polinomial, pré-processa uma determinada instância e gera uma instância cujo tamanho é delimitado no parâmetro. O objetivo da kernelização é (pelo menos) duas vezes. Temos garantias de desempenho comprováveis, ou seja, podemos provar limites superiores na instância de saída, que possui aplicativos tanto no design de algoritmos quanto também como uma medida de complexidade.
Mais formalmente, um algoritmo de kernelização (geralmente chamado de kernel), é um algoritmo para um problema que em uma entrada ( G , k )(G,k)gera uma instância equivalente (G′,k′)(G′,k′) com max { |G′| ,k′} ≤ f( K )max{|G′|,k′}≤f(k) para alguma função ff. Além disso, o algoritmo precisa ser executado em tempo polinomial.
O resultado a seguir mostra que o poder dos núcleos é, por assim dizer, equivalente ao poder da rastreabilidade de parâmetros fixos ( PDF )
Teorema (Folclore). Um problema é um parâmetro fixo tratável se e somente se ele admite um kernel e é decidível.
Embora a noção de kernel coincida com a rastreabilidade dos parâmetros fixos, há uma versão mais forte da kernelização em que exigimos a função ff acima para ser um polinômio.
Se você quiser ver as definições originais, aconselho que você escolha o livro de Downey e Fellows sobre complexidade parametrizada ou comece na tese de Niedermeier sobre Habilitação mencionada acima. Há também um artigo da Wikipedia sobre Kernelization .
Muito obrigado, isso torna as coisas mais claras! Então, basicamente, o objetivo da kernelização é obter uma instância menor do problema, limitada apenas a k, para que você possa resolver o problema na instância menor em O (f (k)) e obter o tempo de execução combinado (= calculando o kernel + resolvendo a nova instância) de algo como O (f (k) + p (n)) que é bom para k pequeno?
— 27516 Peter W
A nota "(Folclore)" sugere que não temos uma prova formal. Parece que me lembro de um, no entanto. Como devemos interpretar o que você escreve?
@Raphael, a atribuição mais antiga (eu acredito) é Habilitationsschrift (2002) de Rolf Niedermeier , que foi publicado como monografia em 2006, mas mesmo nesse ponto ele afirma sem referência: "Finalmente, vamos mencionar de passagem na complexidade parametrizada teoria, tornou-se comum que "todo problema tratável de parâmetro fixo seja kernelizável". ". Daí a atribuição mais tradicional ao folclore.
Isso é engraçado, Rolf Niedermeier é o professor que vai me testar em breve.
— 27615 Peter W
@LukeMathieson Lemma 4.8 (p. 31) de Complexidade parametrizada: Uma estrutura para enfrentar sistematicamente a intratabilidade computacional, Downey, Fellows e Stege, 1997 é: "Um problema parametrizadoeueuestá no FPT se, e somente se, é kernelizable ". ( PDF )