Teoria de la complexitat computacional: diferència entre les revisions

 

Es considera que un problema és inherentment difícil si la seva solució requereix recursos importants, sigui quin sigui l'algorisme utilitzat. La teoria formalitza aquesta intuïció, introduint models matemàtics de càlcul per estudiar aquests problemes i quantificant-ne [[Complexitat computacional|la complexitat computacional]], és a dir, la quantitat de recursos necessaris per resoldre'ls, com el temps i la necessitat d'emmagatzematge. També s'utilitzen altres mesures de complexitat, com ara la quantitat de comunicació (utilitzada en complexitat de comunicació), el nombre de [[Porta lògica|portes]] en un circuit (utilitzat en [[complexitat de circuits]]) i el nombre de processadors (utilitzat en [[Computació paral·lela|informàtica paral·lela]]). Una de les funcions de la teoria de la complexitat computacional és determinar els límits pràctics del que els ordinadors poden i no poden fer. El [[P versus NP|problema P versus NP]], un dels set [[Premi dels problemes del mil·lenni|problemes del Premi del Mil·lenni]], està dedicat al camp de la complexitat computacional.<ref>{{Ref-web|títol=P vs NP Problem {{!}} Clay Mathematics Institute|url=http://www.claymath.org/millennium-problems/p-vs-np-problem|obra=www.claymath.org|llengua=en}}</ref>