Temps polin??mic
De Viquip??dia
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??? enlloc de ???temps s??per-polin??mic???, que ??s m??s lent. Temps exponencial ??s un exemple de temps super-polin??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 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).
[edita] Subclasses de temps polin??mic
- Temps Constant: O(1)
- Temps Lineal: O(n)
- Temps Quadr??tic: O(n2)
- Temps C??bic: O(n3)
[edita] Vegeu tamb??
- Teoria de complexitat
- Temps Exponencial
- P versus NP
- NP
- Algorisme
- O
