Teoria de la complexitat computacional: diferència entre les revisions
Contingut suprimit Contingut afegit
Redirigeix cap a Complexitat computacional |
Creada per traducció de la pàgina «Computational complexity theory» Etiquetes: Redirecció suprimida traducció de contingut ContentTranslation2 |
||
Línia 1:
'''La teoria de la complexitat computacional''' se centra a classificar problemes computacionals segons el seu ús de recursos i relacionar aquestes classes entre si. Un problema computacional és una tasca resolta per un ordinador. Un problema de càlcul es pot resoldre mitjançant l'aplicació mecànica de passos matemàtics, com ara un [[algorisme]].
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>
Camps estretament relacionats en [[Informàtica teòrica|la informàtica teòrica]] són l'[[anàlisi d'algorismes]] i [[Teoria de la computabilitat|la teoria de la computabilitat]]. La primera es dedica a analitzar la quantitat de recursos que necessita un algorisme en particular per resoldre un problema, mentre que la segona fa una pregunta més general sobre tots els possibles algorismes que es podrien utilitzar per resoldre el mateix problema. Més concretament, la teoria de la complexitat computacional intenta classificar problemes que es poden o no resoldre amb recursos restringits adequadament. Al seu torn, imposar restriccions als recursos disponibles és el que distingeix la complexitat computacional de la teoria de la computabilitat: aquesta darrera teoria es pregunta quin tipus de problemes es poden, en principi, resoldre algorítmicament.
== Referències ==
=== Llibres de text ===
* {{Citation|last1=Arora|first1=Sanjeev|last2=Barak|first2=Boaz|title=Computational Complexity: A Modern Approach|url=http://www.cs.princeton.edu/theory/complexity/|publisher=Cambridge University Press|year=2009|isbn=978-0-521-42426-4}}
* {{Citation|last1=Downey|first1=Rod|last2=Fellows|first2=Michael|title=Parameterized complexity|url=https://www.springer.com/sgw/cda/frontpage/0,11855,5-0-22-1519914-0,00.html|publisher=Springer-Verlag|year=1999|isbn=9780387948836}}
* {{Citation|last1=Du|first1=Ding-Zhu|last2=Ko, Ker-I|title=Theory of Computational Complexity|publisher=John Wiley & Sons|year=2000|isbn=978-0-471-34506-0}}
*
* {{Citation|last1=Goldreich|first1=Oded|url=http://www.wisdom.weizmann.ac.il/~oded/cc-book.html|title=Computational Complexity: A Conceptual Perspective|publisher=Cambridge University Press|year=2008}}
* {{Citation|editor-first=Jan|editor2-last=Jan van Leeuwen|title=Handbook of theoretical computer science (vol. A): algorithms and complexity|publisher=MIT Press|isbn=978-0-444-88071-0|year=1990}}
* {{Citation|last1=Papadimitriou|first1=Christos|title=Computational Complexity|edition=1st|year=1994|publisher=Addison Wesley|isbn=978-0-201-53082-7}}
* {{Citation|last1=Sipser|first1=Michael|title=Introduction to the Theory of Computation|edition=2nd|year=2006|publisher=Thomson Course Technology|isbn=978-0-534-95097-2}}
[[Categoria:Complexitat computacional]]
| |||