Temps polinòmic
En teoria de complexitat, temps polinòmic es refereix al temps de computació d'un problema on el temps, m(n), no és major que una funció polinòmica de la mida del problema, n. Donada qualsevol màquina abstracta tindrà una classe de complexitat corresponent als problemes que es poden resoldre en temps polinòmic en dita màquina.
Escrivint-ho matemàticament, m(n) = O (nk) on k és una constant (que depèn del problema).
En matemàtiques alguns cops s'usa la notació "temps polinòmic respecte la longitud d'entrada" com de definició d'una computació "ràpida" en lloc de "temps súper-polinòmic", que és més lent. Temps exponencial és un exemple de temps superpolinòmic.
La classe de complexitat dels problemes de decisió que es poden resoldre en una màquina seqüencial determinista em temps polinòmic es coneix com a P. La classe dels problemes de decisió que es poden verificar en temps polinòmic es coneix per NP. De manera equivalent, NP és una classe de problemes de decisió que es poden resoldre en temps polinòmic en una Màquina de Turing no determinista (NP significa Nondeterministic Polynomial time).
Subclasses de temps polinòmic
[modifica]- Temps Constant: O (1)
- Temps Lineal: O (n)
- Temps Quadràtic: O (n²)
- Temps Cúbic: O (n3)