# Complexité

la **Complexité** \\( A \\) est une fonction non décroissante \\( f_A(k) \\) le nombre
d'instructions caractéristiques éxécuté par A pour une donnée de taille \\( k \\) 

On parle de la **compléxité d'un problème** lorsque c'est celle du meilleur algo connu pour résoudre
ce problème.

Un problème d'optimisation est 
\\[
    f(s^*) = \min_{s \in S}\\{f(s)\\} 
\\] 

Un problème d'éxistance est un sous problème d'optimisation ou tq 

Un problème d'optimisation est au moins aussi difficile que le problème d'existance associé

- **facile**: existe un algorithme polynomiale
- **difficile**: n'existe pas actuellement.

On donne la class **P** aux problèmes polynominaux et **NP** aux problème *vérifiables* en temps
polynominal.

\\[
    NP \subseteq P
\\]
