cours/classe de complexité FPT.md

up, tags, aliases

up	tags	aliases
complexité algorithmique	s/informatique

[!definition] Définition

^definition

Propriétés

[!proposition]+ Les 3 propositions suivantes sont équivalentes

1. (L, K) \in FPT algo pour décider L en temps f(K(x)) \cdot |x|^{O(1)} (f calculable)
2. On peut décider L en temps g(K(x)) + |x|^{O(1)} (g calculable)
3. On peut décider L en temps h_1(K(x)) + (h_2(K(x)) + |x|)^{O(1)} (h_1, h_2 calculables)

[!démonstration]- Démonstration 1. \implies 2. car (f(K(x)) \cdot |x|^{C}) \leq f(K(x))^{2} + |x|^{2C} 2. \implies 3. est trivial 3. \implies 1. sans perte de généralité : \forall k,\quad h_1(k) \geq 2 et \forall k,\quad h_2(k) \geq 2

Exemples