---
up:
  - "[[complexité algorithmique]]"
tags:
  - s/informatique
aliases:
---


> [!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