Diferència entre revisions de la pàgina «Temps polinòmic»

m
cap resum d'edició
m
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 (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==
468

modificacions