Teoria de la complexitat computacional
Plantilla:PA La teoria de la complexitat computacional és una subdisciplina de la teoria de la computació que estudia la dificultat intrínseca dels problemes computacionals i categoriza dits problemes en classes de complexitat segons els recursos necessaris per a resoldre'ls, com el temps d'eixecució i l'us de memòria.
L'objectiu principal d'esta teoria és comprendre les llimitacions fonamentals de la computació eficient, és dir, quins problemes poden resoldre's en un temps raonable per mig d'algoritmes determinista o no determinista, i quins requerixen recursos computacionals que creixen de forma exponencial o inclús no són resolubles. Un eixemple clàssic és el problema de determinar si la classe de problemes que poden resoldre's en temps polinomial (denotada com P) és igual a la classe de problemes la solució dels quals pot verificar-se en temps polinomial (denotada com NP), conegut com el problema P vs NP.
Les classes de complexitat permeten comparar l'eficiència d'algoritmes i establir llímits teòrics a lo que és computacionalment possible. La teoria també investiga conceptes com reduccions entre problemes, completitud, durea, i jerarquia de classes com PSPACE, EXPTIME, entre unes atres.[1]
Un problema es cataloga com "inherentemente complex" si la seua solució requerix d'una cantitat significativa de recursos computacionals, sense importar l'algoritme utilisat. La teoria de la complexitat computacional formalisa dita asseveració, introduint models de computació matemàtics per a l'estudi d'estos problemes i la quantificació de la cantitat de recursos necessaris per a resoldre'ls, com a temps i memòria.
Una de les metes de la teoria de la complexitat computacional és determinar els llímits pràctics de qué és lo que es pot fer en una computadora i qué no. Atres camps relacionats en la teoria de la complexitat computacional són l'anàlisis d'algoritmes i la teoria de la computabilidad. Una diferència significativa entre l'anàlisis d'algoritmes i la teoria de la complexitat computacional, és que el primer es dedica a determinar la cantitat de recursos requerits per un algoritme en particular per a resoldre un problema, mentres que la segona, analisa tots els possibles algoritmes que pogueren ser usats per a resoldre el mateix problema.
La teoria de la complexitat computacional tracta de classificar els problemes que poden, o no poden ser resolts en una cantitat determinada de recursos. A la seua volta, l'imposició de restriccions sobre estos recursos, és lo que la distinguix de la teoria de la computabilidad, la qual es preocupa per qué tipo de problemes poden ser resolts de manera algorítmica.
Història
[editar | editar còdic]Ans que es realisaren investigacions entorn a la complexitat dels algoritmes, es varen crear els fonaments d'esta teoria per varis investigadors. Un dels aportes més influents va ser la definició de les màquines de Turing en 1936,[2] les quals varen resultar ser una noció de computadora molt flexible i robusta. A mida que les computadores es desenrollaven en els 40's i els 50's, la Màquina de Turing va demostrar ser el model teòric correcte de còmput.
No obstant, ràpidament es va descobrir que el model bàsic de la màquina de Turing fallava en quantificar el temps i la memòria requerida per una computadora, un problema crític hui en dia, i encara més en aquells temps. L'idea de medir el temps i espai com una funció de la llongitut de l'entrada es va originar a principis dels 60s per Hartmanis i Stearns, i aixina va nàixer la teoria de la complexitat computacional.
En els inicis, els investigadors tractaven d'entendre les noves mides de complexitat, i cóm es relacionaven unes en unes atres. En 1965, Edmonds va definir un "bon" algoritme com un en un temps d'eixecució acotat per un polinomi, és dir, en un temps d'eixecució polinòmic.[3] Açò va conduir al sorgiment d'un dels conceptes més importants de la teoria de la complexitat computacional: la NP-completitud i la seua pregunta fonamental, si P=NP.
El camp va començar a florir quan l'investigador nortamericà Stephen Cook i el soviètic Leonid Levin, treballant de manera independent, varen provar que existixen problemes rellevants que són NP-complets. En 1972, Richard Karp va dur esta idea un pas més alvance, demostrant que 21 problemes combinatoris i de teoria de grafos, caracterisats per ser computacionalment intractables, eren NP-complets.[4] També en els 70's, es va produir un creiximent de les classes de complexitat a mida que els investigadors tractaven de comprendre els distints models de còmput existents.
En els 80's, es va produir un auge dels models finitos, que analisaven el procés de còmput d'una manera inherentemente distinta. Va sorgir un nou acostament a problemes com a P=NP, i aun cuando estos models tenien les seues llimitacions separant les classes de complexitat, esta aproximació va introduir tècniques combinatòries que varen permetre un millor enteniment dels llímits d'estos models.
Ya en els 90's, es varen estudiar nous models de còmput com les computadores quàntiques, a on una mateixa tasca pot tindre diferent complexitat en la computació clàssica i en la computació quàntica. No obstant, existixen vàries limitantes, entre elles, la de desenrollar un hardware per a este model, i que es requerixen grans cantitats d'espai per a realisar els càlculs.
Problemes, algoritmes i complexitat
[editar | editar còdic]Per a poder referir-nos a problemes com "inherentemente intractables" i problemes de dificultat "equivalent", és necessari comprendre alguns térmens més bàsics.[5]
Problema computacional
[editar | editar còdic]- Artícul principal → Problema computacional.
Un problema computacional constituïx una pregunta a ser resposta, tenint generalment varis paràmetros, o variables lliures, els valors de les quals no s'han especificat. Un problema es descriu per mig de:
- Una descripció general de tots els seus paràmetros (poden ser d'entrada o d'eixida).
- Una sentència que descriga les propietats que la resposta, o la solució, deu complir.
Una instància d'un problema s'obté quan s'especifiquen valors particulars per a tots els paràmetros del problema. Per eixemple, considerem el problema del test de primalidad. L'instància és un número (i.g. 15) i la solució és "sí" si el número és primer, i "no" en cas contrari. Vist d'una atra manera, l'instància és una entrada particular del problema, i la solució és l'eixida corresponent per a l'entrada donada.
Problemes de decisió
[editar | editar còdic]- Artícul principal → Problema de decisió.
Un problema de decisió és un tipo especial de problema computacional la resposta del qual és solament "sí" o "no" (o, de manera més formal, "1" o "0").
Un problema de decisió poguera vore's com un llenguage formal, a on els elements que pertanyen al llenguage són les instàncies del problema la resposta del qual és "sí", els que no pertanyen al llenguage són aquelles instàncies la resposta de les quals és "no". L'objectiu és decidir, en l'ajuda d'un algoritme, si una determinada entrada és un element del llenguage formal considerat. Si l'algoritme torna com a resposta "sí", es diu que l'algoritme accepta l'entrada, de lo contrari es diu que la rebuja.
Els problemes de decisió constituïxen un dels principals objectes d'estudi de la teoria de la complexitat computacional, puix la NP-completitud s'aplica directament a estos tipos de problemes en lloc de problemes d'optimisació. Estos problemes tenen gran importància perque casi tot problema pot transformar-se en un problema de decisió.
Algoritmes
[editar | editar còdic]- Artícul principal → Algoritme.
Podem dir informalmente, que els algoritmes són procediments passe-a-pas per a resoldre problemes. Es pot pensar en ells com a simples programes de computadora, escrits en un llenguage artificial específic.[6]
Es diu que un algoritme resol un problema A, si dit algoritme es pot aplicar a qualsevol instància I de A, i es garantisa que sempre produïx una solució per a dita instància. De manera general, nos interessa trobar l'algoritme més "eficient" per a resoldre cert problema. En el seu sentit més ampli, la noció d'eficiència involucra a tots els recursos computacionals necessaris per a l'eixecució d'un algoritme.
Per algoritme "més eficient" usualment nos referim al més ràpit. Degut a que els requeriments de temps són usualment un factor dominant quan es tracta de determinar si un algoritme és lo suficientment eficient per a ser útil en la pràctica, nos concentrarem en este recurs.
Algoritmes de temps polinòmic i problemes intractables
[editar | editar còdic]Els científics de la computació realisen la distinció entre algoritmes de Temps polinòmic i algoritmes de temps exponencial quan es tracta de caracterisar als algoritmes com "suficientment eficient" i "molt ineficiente" respectivament.
Un algoritme de temps polinomial es definix com aquell en funció de complexitat temporal dins d'una cota superior asintòtica (denominada a voltes "orde") O(p(n)) per a alguna funció polinòmica p, a on n denota el tamany de l'entrada. Els algoritmes de temps exponencial, són els que el número de cicles que tenen que realisar-se en l'algoritme és proporcional a la funció de modo que el poder computacional necessari per a córrer l'algoritme creix de forma exponencial al tamany del problema.
La majoria dels algoritmes de temps exponencial són simples variacions d'una busca exhaustiva, mentres que els algoritmes de temps polinomial, usualment s'obtenen per mig d'un anàlisis més profunt de l'estructura del problema. En la teoria de la complexitat computacional, existix el consens de que un problema no està "ben resolt" fins que es conega un algoritme de temps polinomial que ho resolga. Per tant, nos referirem a un problema com a intractable, si és tan difícil que no existix algoritme de temps polinomial capaç de resoldre-ho.[7]
Vore també
[editar | editar còdic]- Complexitat computacional de les operacions matemàtiques
- Reducció (complexitat)
- Teorema de Cook-Levin
- Llista de 21 problemes NP-complets de Karp
- Classes de complexitat P i NP
- Teorema de la jerarquia temporal
- Anex:Classes de complexitat
- Complexitat de Kolmogórov
Referències
[editar | editar còdic]- ↑ «Computational Complexity Theory» (en anglés). Metaphysics Research Lab, Stanford University.
- ↑ Senen Fanc (2002). «1», Fronteres de la computació, 2 edició, Diaz de Sants, pp. 11. ISBN 9788479785178.
- ↑ Richard M. Karp, "Combinatorics, Complexity, and Randomness", 1985 Turing Award Lecture.
- ↑ Richard M. Karp(1972).«Complexity of Computer Computations».New York: Plenum.
- 85–103.Consultat el 21 de decembre de 2012..
- ↑ García Merayo (2015). «11.3», Matemàtica discreta, 3 edició, Edicions Paraninfo, S.A, pp. 548. ISBN 978-84-283-3568-3.
- ↑ Garey, Michael R., Johnson David S., (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, (page 4).
- ↑ Garey, Michael R., Johnson David S., (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, (page 8).
Referències
[editar | editar còdic]
- Este artícul conté una traducció derivada de «Teoría de la complejidad computacional» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.