31 lines
774 B
Markdown
31 lines
774 B
Markdown
---
|
|
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
|
|
|