Temps polinòmic: diferència entre les revisions
mCap resum de modificació |
|||
| Línia 5: | Línia 5: | ||
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. |
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 [[problema de decisió|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 (Complexitat) | 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 '''N'''ondeterministic '''P'''olynomial time). |
La [[classe de complexitat]] dels [[problema de decisió|problemes de decisió]] que es poden resoldre en una màquina seqüencial determinista em temps polinòmic es coneix com '''[[P (Complexitat)|P]]'''. La classe dels problemes de decisió que es poden verificar en temps polinòmic es coneix per '''[[NP (Complexitat) | 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 '''N'''ondeterministic '''P'''olynomial time). |
||
==Subclasses de temps polinòmic== |
==Subclasses de temps polinòmic== |
||
Revisió del 00:16, 4 juny 2007
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 depen 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).
Subclasses de temps polinòmic
- Temps Constant: O(1)
- Temps Lineal: O(n)
- Temps Quadràtic: O(n2)
- Temps Cúbic: O(n3)