La teoría de la complexidá computacional ye una caña de la teoría de la computación que se centra na clasificación de los problemes computacionales d'alcuerdu a la so dificultá inherente, y na rellación ente felicidaes clases de complexidá.
Un problema catalógase como "inherentemente difícil" si la so solución rique d'una cantidá significativa de recursos computacionales, ensin importar l'algoritmu utilizáu. La teoría de la complexidá computacional formaliza felicidá aseveración, introduciendo modelos de cómputu matemáticos pal estudiu d'estos problemes y la cuantificación de la cantidá de recursos necesarios pa resolvelos, como tiempu y memoria.
Unu de los fines de la teoría de la complexidá computacional ye determinar les llendes práutiques de qué ye lo que puede faese nun ordenador y qué non. Otros campos rellacionaos cola teoría de la complexidá computacional son el analís d'algoritmos y la teoría de la computabilidad. Una diferencia significativa ente l'analís d'algoritmos y la teoría de la complexidá computacional, ye que'l primeru dedicar a determinar la cantidá de recursos riquíos por un algoritmu en particular pa resolver un problema, ente que la segunda, analiza tolos posibles algoritmos que pudieren ser usaos pa resolver el mesmu problema.
La teoría de la complexidá computacional trata de clasificar los problemes que pueden, o nun pueden ser resueltos con una cantidá determinada de recursos. De la mesma, la imposición de restricciones sobre estos recursos, ye lo que la estrema de la teoría de la computabilidad, que esmolezse por qué tipu de problemes pueden ser resueltos de manera algorítmica.
Historia
Primero que se realizaren investigaciones en redol a la complexidá de los algoritmos, creáronse los cimientos d'esta teoría por dellos investigadores. Unu d'apurrir más influyentes foi la definición de les máquines de Turing en 1936, que resultaron ser una noción d'ordenador bien flexible y robusta. A midida que los ordenadores desenvolver nos 40's y los 50's, la Máquina de Turing demostró ser el modelu teóricu correutu de cómputu.
Sicasí, rápido afayóse que'l modelu básicu de la máquina de Turing fallaba al cuantificar el tiempu y la memoria riquida por un ordenador, un problema críticu anguaño, y entá más naquellos tiempos. La idea de midir el tiempu y espaciu como una función del llargor de la entrada, aniciar a principios de los 60's por Hartmanis and Stearns, y asina, nació la teoría de la complexidá computacional.
Nos entamos, los investigadores trataben d'entender les nueves midíes de complexidá, y cómo se rellacionaben unes con otres. En 1965, Edmonds definió un "bon" algoritmu como unu con un tiempu d'execución acutáu por un polinomiu, esto ye, con un tiempu d'execución polinómico.[1] Esto condució al surdimientu d'unu de los conceutos más importantes de la teoría de la complexidá computacional: la NP-completitud y la so entruga fundamental, si P=NP.
El campu empezó a floriar cuando'l investigadores Stephen Cook, norteamericanu, Leonid Levin, sovietico, trabayando de manera independiente, probaron qu'esisten problemes relevantes que son NP-completos. En 1972, Richard Karp llevó esta idea un pasu más palantre, demostrando que 21 problemes combinatorios y de teoría de grafos, carauterizaos por ser computacionalmente intratables, yeren NP-completos.[2] Tamién nos 70's, producióse una crecedera de les clases de complexidá a midida que los investigadores trataben d'entender los distintos modelos de cómputu esistentes.
Nos 80's, producióse una puxanza de los modelos finitos, qu'analizaben el procesu de cómputu d'una manera inherentemente distinta. Surdió un nuevu acercamientu a problemes como P=NP, ya inda cuando estos modelos teníen les sos llimitaciones dixebrando les clases de complexidá, esti aproximamientu introdució téuniques combinatories que dexaron un meyor entendimientu de les llendes d'estos modelos.
Yá nos 90's, estudiáronse nuevos modelos de cómputu como les ordenadores cuánticos, onde una mesma xera puede tener distinta complexidá na computación clásica y na computación cuántica. Sicasí, esisten delles limitantes, ente elles, la de desenvolver un hardware pa esti modelu, y que se riquir grandes cantidaes d'espaciu pa realizar los cálculos.
Problemes, algoritmos y complexidá
Pa poder referinos a problemes como "inherentemente intratables" y problemes de dificultá "equivalente", ye necesariu entender dellos términos más básicos.
Problema computacional
Un problema computacional constitúi una entruga a ser respondida, teniendo xeneralmente dellos parámetros, o variables llibres, que los sos valor non se especificaron. Un problema describir por aciu:
- Una descripción xeneral de tolos sos parámetros (pueden ser d'entrada o de salida).
- Una sentencia que describa les propiedaes que la respuesta, o la solución, tien de cumplir.
Una instancia d'un problema llógrase cuando s'especifiquen valores particulares pa tolos parámetros del problema. Por casu, consideremos el problema del test de primalidad. La instancia ye un númberu (e.g. 15) y la solución ye "sí" si'l númberu ye primu, y "non" en casu contrariu. Vistu d'otra manera, la instancia ye una entrada particular del problema, y la solución ye la salida correspondiente pa la entrada dada.
Problemes de decisión
Un problema de decisión ye un tipu especial de problema computacional que la so respuesta ye solamente "sí" o "non" (o, de manera más formal, "1" o "0").
Un problema de decisión pudiera trate como un llinguaxe formal, onde los elementos que pertenecen al llinguaxe son les instancies del problema que la so respuesta ye "sí", los que nun pertenecen al llinguaxe son aquelles instancies que la so respuesta ye "non". L'oxetivu ye decidir, cola ayuda d'un algoritmu, si una determinada entrada ye un elementu del llinguaxe formal consideráu. Si l'algoritmu devuelve como respuesta "sí", dizse que l'algoritmu acepta la entrada, de lo contrario dizse que la refuga.
Los problemes de decisión constitúin unu de los principales oxetos d'estudiu de la teoría de la complexidá computacional, pos la NP-completitud aplícase direutamente a estos tipos de problemes en cuenta de a problemes de optimización. Estos problemes tienen gran importancia porque casi tou problema puede tresformase nun problema de decisión.
Algoritmos
Podemos dicir informalmente, que los algoritmos son procedimientos paso-a-pasu pa resolver problemes. Puede pensase nellos como simples programes d'ordenador, escritos nun llinguaxe artificial específicu.[3]
Dizse qu'un algoritmu resuelve un problema A, si dichu algoritmu puede aplicase a cualquier instancia I d'A, y garantízase que siempres produz una solución pa dicha instancia. De manera xeneral, interésanos atopar l'algoritmu más "eficiente" pa resolver ciertu problema. Nel so sentíu más ampliu, la noción d'eficiencia arreya a tolos recursos computacionales necesarios pa la execución d'un algoritmu.
Por algoritmu "más eficiente" usualmente referímonos al más rápidu. Por cuenta de que los requerimientos de tiempu son usualmente un factor dominante cuando se trata de determinar si un algoritmu ye lo suficientemente eficiente pa ser útil na práutica, vamos concentranos nesti recursu.
Algoritmos de tiempu polinómico y problemes intratables
Los científicos de la computación realicen la distinción ente algoritmos de Tiempu polinómico y algoritmos de tiempu esponencial cuando se trata de carauterizar a los algoritmos como "abondo eficiente" y "bien ineficiente" respeutivamente.
Un algoritmu de tiempu polinomial defínese como aquel con función de complexidá temporal n'O(p(n)) pa dalguna función polinómica p, onde n denota el tamañu de la entrada. Cualquier algoritmu que la so función de complexidá temporal nun pueda ser acutada d'esta manera, denominar algoritmu de tiempu esponencial.
La mayoría de los algoritmos de tiempu esponencial son simples variaciones d'una busca refecha, ente que los algoritmos de tiempu polinomial, usualmente llograr por aciu un analís más fondu de la estructura del problema. Na teoría de la complexidá computacional, esiste'l consensu de qu'un problema nun ta "bien resueltu" hasta que se conoza un algoritmu de tiempu polinomial que lo resuelva. Por tanto, vamos referinos a un problema como intratable, si ye tan difícil que nun esiste algoritmu de tiempu polinomial capaz de resolvelo.[4]
Clases de complexidá
{{AP|Clase de complexidá Una clase de complexidá ye un conxuntu de problemes que tienen la mesma complexidá computacional.
Definiendo clases de complexidá
Les clases de complexidá más sencielles defínense teniendo en cuenta factores como:
- El tipu de problema computacional: Los problemes más comúnmente utilizaos son los problemes de decisión, pero les clases de complexidá pueden definise pa otros tipos de problemes.
- El modelu de cómputu: El modelu de cómputu más común ye la Máquina de Turing determinista, pero munches clases de complexidá basar en Máquines de Turing non deterministes, Máquines de Turing cuántiques, etc.
- El recursu (o recursos) que ta(n) siendo acutáu(s) y la(s) cota(s): Estos dos propiedaes usualmente utilícense xuntes, por casu, "tiempu polinomial", "espaciu logarítmicu", "fondura constante", etc.
Máquines de Turing deterministes y la clase P
La clase P contién a aquellos problemes que son solubles en tiempu polinómico por una máquina de Turing determinista.[5]
Pa la definición anterior afitóse'l modelu de cómputu: la Máquina de Turing determinista. Esisten distintes variantes de la Máquina de Turing y ye conocíu que la más débil d'elles puede asemeyar a la más fuerte, amestando a lo sumo un tiempu polinómico. Nes décades posteriores a la Tesis de Church-Turing surdieron otros modelos de cómputu, y pudo amosase que la Máquina de Turing tamién podía asemeyalos a lo sumo amestando tamién un tiempu polinómico. Poro, la clase análoga a P para dichos modelos nun ye mayor que la clase P pal modelu de cómputu de la máquina de Turing.
La clase P xuega un papel importante na teoría de la complexidá computacional por cuenta de que:
- P ye invariante pa tolos modelos de cómputu que son polinómicamente equivalentes a la Máquina de Turing determinista.
- A les traces, P correspuende a la clase de problemes que, de manera realista, son solubles nun ordenador.
Computación non determinista y la clase NP
Munches vegaes podemos evitar utilizar la fuercia bruto nos problemes pa llograr soluciones en tiempu polinómico. Sicasí, pa dellos problemes esto nun pudo llograse, esto ye, nun se conocen algoritmos que los resuelvan en tiempu polinómico. Quiciabes estos problemes tengan algoritmos en tiempu polinomial que se basen en principios dica agora desconocíos, o quiciabes estos problemes non pueden ser resueltos en tiempu polinómico, por cuenta de que son "inherentemente difíciles".
La clase de complexidá NP consta de los problemes "verificables" en tiempu polinómico. Por verificable entender a un problema tal que dau un certificáu de solución (candidatu a solución), puede verificase que dichu certificáu ye correutu nun tiempu polinómico nel tamañu de la entrada. A los problemes na clase NP usualmente llámase-yos problemes NP.[6]
El términu NP provién de non determinista en tiempu polinómico y derívase d'una carauterización alternativa d'esta clase, onde s'utilicen Máquines de Turing non deterministes. Informalmente, puede definise la clase NP en términos d'un algoritmu non determinista (recordar la equivalencia ente algoritmu y Máquina de Turing).
L'algoritmu mentáu ta compuestu por 2 etapes separaes. Dada una instancia del problema I, la primer etapa a cencielles "adivina" un candidatu a solución S. Entós, la etapa de verificación recibe como entrada a I y a S, y da en realizar el cómputu d'una manera determinista, finalmente deteniéndose cola respuesta "sí", o cola respuesta "non", o sigue computando ensin detenese.
Al igual que la clase P, la clase NP ye insensible a la eleición del modelu de cómputu non determinista, por cuenta de que dichos modelos son equivalentes polinómicamente.
Clases de complexidá importantes
Munches clases de complexidá importantes pueden ser definíes acutando'l tiempu o l'espaciu utilizáu pol algoritmu. Dalgunes d'estes clases de problemes de decisión son:
| Clase de complexidá | Modelu de cómputu | Restricción de recursu |
|---|---|---|
| DTIME(f(n)) |
Tiempu f(n) | |
| P |
Tiempu poly(n) | |
| PP |
Tiempu poly(n) | |
| EXPTIME |
Tiempu 2poly(n) | |
| NTIME(f(n)) |
Tiempu f(n) | |
| NP |
Tiempu poly(n) | |
| NEXPTIME |
Tiempu 2poly(n) | |
| DSPACE(f(n)) |
Espaciu f(n) | |
| L |
Espaciu O(log n) | |
| PSPACE |
Espaciu poly(n) | |
| EXPSPACE |
Espaciu 2poly(n) | |
| NSPACE(f(n)) |
Espaciu f(n) | |
| NL |
Espaciu O(log n) | |
| NPSPACE |
Espaciu poly(n) | |
| NEXPSPACE |
Espaciu 2poly(n) |
La entruga P=NP
La rellación ente les clases P y NP ye fundamental pa la teoría de la NP-completitud. Intuitivamente, creemos que P ye un subconxuntu de NP. Y, efeutivamente, cada problema de decisión resueltu por un algoritmu de tiempu polinomial determinista, tamién puede ser resueltu por un algoritmu de tiempu polinomial non determinista. A cencielles precísase reparar que cualquier algoritmu determinista pue ser utilizáu na etapa de verificación d'un algoritmu non determinista. Si B ye un problema de P, y A ye un algoritmu de tiempu polinomial pa B, entós puede construyise un algoritmu de tiempu polinomial non determinista pa B, a cencielles utilizando A na etapa de verificación ya inorando la etapa d'aldovinación. Por tanto, si B pertenez a P, entós B tamién pertenez a NP.
La entruga P=NP ye una de les más importantes nel campu de les ciencies de la computación, por cuenta de les grandes repercusiones qu'habría, en casu d'atopase una solución. Si P=NP, cualquier problema polinómicamente verificable sería polinómicamente decidible. La mayoría de los investigadores cree qu'estes clases nun son iguales, porque se realizó bastantes esfuercios, ensin ésitu, p'atopar algoritmos de tiempu polinomial pa dellos problemes en NP. Los investigadores tamién trataron de probar que les clases son distintes, pero eso traería a amosar que nun esiste un algoritmu eficiente» pa reemplazar a la busca por fuercia bruto.
NP-Completitud
Amenorgamientu polinomial
Un amenorgamientu ye un tresformamientu d'un problema n'otru problema. Intuitivamente, un problema Q pue ser amenorgáu a otru problema Q', si cualquier instancia del problema Q pue ser "fácilmente" espresada como una instancia del problema Q', y que la so solución apurra una solución pa la instancia de Q.[7]
Esisten munchos tipos d'amenorgamientos: basaes nel métodu d'amenorgamientu, como los amenorgamientos de Cook, los amenorgamientos de Karp y los amenorgamientos de Levin, y les basaes na cota de la complexidá, como la amenorgamientu en tiempu polinomial o l'amenorgamientu d'espaciu logarítmica. Una de los amenorgamientos más utilizaos ye l'amenorgamientu en tiempu polinomial, lo cual significa que'l procesu d'amenorgamientu toma un tiempu polinomial.
Problemes NP-completos
Los amenorgamientos en tiempu polinomial dótennos d'elementos pa probar, d'una manera formal, qu'un problema ye siquier tan difícil qu'otru, con una diferencia d'un factor polinomial. Estes son esenciales pa definir a los problemes NP-completos, amás d'ayudar a entender los mesmos.
La clase de los problemes NP-completos contién a los problemes más difíciles en NP, nel sentíu de que son los que tean más lloñe de tar en P. Por cuenta de que el problema P=NP nun foi resueltu, el fechu d'amenorgar un problema B, a otru problema A, indicaría que nun se conoz solución en tiempu polinomial para A. Esto ye por cuenta de que una solución en tiempu polinomial para A, tendría de resultes la esistencia d'una solución polinomial pa B. De manera similar, por cuenta de que tolos problemes NP pueden ser amenorgaos a esti conxuntu, atopar un problema NP-completu que pueda ser resueltu nun tiempu polinomial significaría que P=NP.
Importancia de la NP-Completitud
Quiciabes la razón de mayor pesu pola cual los científicos de la computación creen que P ye distintu de NP, ye la esistencia de la clase de problemes "NP-completos". Esta clase tien la interesada propiedá de que si dalgún problema NP-completu pue ser resueltu en tiempu polinomial, entós tou problema en NP tien una solución en tiempu polinomial, esto ye, P=NP. A pesar d'años d'estudiu, nengún algoritmu de tiempu polinomial afayóse pa nengún problema NP-completu.
Dende'l puntu de vista teóricu, un investigador intentando amosar que la clase P ye distinta de la clase NP, pudiera enfocase nun problema NP-completu. Si dalgún problema en NP rique más qu'un tiempu polinomial, entós unu NP-completu tamién. Amás, un investigador intentando demostrar que P=NP, solo precisa atopar un algoritmu de tiempu polinomial pa un problema NP-completu pa llogralo.
Dende'l puntu de vista práuticu, el fenómenu de la NP-completitud puede prevenir la perda de tiempu cuando se busca un algoritmu de tiempu polinomial non esistente pa resolver un problema determináu. Inda cuando nun se tener los elementos matemáticos pa demostrar que ciertu problema nun puede resolvese en tiempu polinomial, creemos que P nun ye igual a NP, asina que demostrar que'l problema ye NP-completu, ye una fuerte evidencia de la so non "polinomialidad".
Faciendo frente a problemes NP
Teniendo en cuenta la definición de problema intratable, si nun se cumple que P=NP, entós los problemes NP-completos son intratables.
Munchos problemes de la práutica son NP-completos, y son bien importantes como p'arrenunciar a cencielles porque nun sabemos cómo atopar una solución óptima en tiempu polinomial. Anque un problema sía NP-completu, puede haber esperanza. Esisten tres estrategia fundamentales pa trepar con un problema NP-completu:
- Si la entrada ye pequeña, un algoritmu con tiempu d'execución esponencial pudiera ser perfectamente aceptable.
- Pudieren aisllase dellos casos especiales que pudieren resolvese en tiempu polinomial.
- Podríamos utilizar aproximamientos p'atopar soluciones lo suficientemente cercanes al óptimo en tiempu polinomial. Na práutica, llograr soluciones cercanes al óptimo ye abondo aceptable. A estos algoritmos denominar algoritmo d'aproximamientu, y en munchos casos sofitar en heurístiques y metaheurísticas.
Ver tamién
- Amenorgamientu (complexidá)
- Teorema de Cook-Levin
- Llista de 21 problemes NP-completos de Karp
- Clases de complexidá P y NP
- Teorema de la xerarquía temporal
- Clases de complexidá
Referencies
- ↑ Richard M. Karp, "Combinatorics, Complexity, and Randomness", 1985 Turing Award Lecture.
- ↑ Richard M. Karp, «Reducibility Among Combinatorial Problems», en R. Y. Miller and J. W. Thatcher (editors), Complexity of Computer Computations, New York: Plenum, pp. 85–103.
- ↑ 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).
- ↑ Cormen, Thomas H.; Leiserson, Charles Y.; Rivest, Ronald L. & Stein, Clifford, (2010), Introduction to Algorithms, 3ª edición, MIT Press and McGraw-Hill, (page 1049).
- ↑ Garey, Michael R., Johnson David S., (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, (page 28).
- ↑ Cormen, Thomas H.; Leiserson, Charles Y.; Rivest, Ronald L. & Stein, Clifford, (2010), Introduction to Algorithms, 3ª edición, MIT Press and McGraw-Hill, (page 1067).
Artículos
- Cook, Stephen, «An overview of computational complexity», Commun. ACM (ACM) 26 (6): 400–408, ISSN 0001-0782
- Fortnow, Lance; Homer, Steven, «A Short History of Computational Complexity», Bulletin of the EATCS 80: 95–133, http://people.cs.uchicago.edu/~fortnow/papers/history.pdf
Llibros de testu
- Arora, Sanjeev; Barak, Boaz, Computational Complexity: A Modern Approach, Cambridge, ISBN 978-0-521-42426-4, http://www.cs.princeton.edu/theory/complexity/
- Sipser, Michael (2006), Introduction to the Theory of Computation (2da edición), USA: Thomson Course Technology, ISBN 0-534-95097-3
- Garey, Michael R.; Johnson, David S., (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5.
- Cormen, Thomas H.; Leiserson, Charles Y.; Rivest, Ronald L. & Stein, Clifford, Introduction to Algorithms (3ra edición), Cambridge, MA: MIT Press and McGraw-Hill, ISBN 0-262-03384-4
| Control d'autoridaes |
|
|---|
Datos: Q205084
Multimedia: Computational complexity theory