Teoría de la complexidá computacional

De Wikipedia
Saltar a navegación Saltar a la gueta

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 nuna computadora 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[editar | editar la fonte]

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 correctu 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, el 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, caracterizaos 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 el 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écniques 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á[editar | editar la fonte]

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[editar | editar la fonte]

Artículu principal: 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:

  1. Una descripción xeneral de tolos sos parámetros (pueden ser d'entrada o de salida).
  2. 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 (y.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[editar | editar la fonte]

Artículu principal: Problema 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[editar | editar la fonte]

Artículu principal: Algoritmu

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[editar | editar la fonte]

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 caracterizar 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á[editar | editar la fonte]

{{AP|Clase de complexidá Una clase de complexidá ye un conxuntu de problemes que tienen la mesma complexidá computacional.

Definiendo clases de complexidá[editar | editar la fonte]

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[editar | editar la fonte]

Artículu principal: P (clase de complexidá)

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:

  1. P ye invariante pa tolos modelos de cómputu que son polinómicamente equivalentes a la Máquina de Turing determinista.
  2. 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[editar | editar la fonte]

Artículu principal: NP (clase de complexidá)

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 dáu un certificáu de solución (candidatu a solución), puede verificase que dichu certificáu ye correctu 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 provien de non determinista en tiempu polinómico y derívase d'una caracterizació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[editar | editar la fonte]

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[editar | editar la fonte]

Artículu principal: Clases de complexidá P y 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 ignorando 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. El 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[editar | editar la fonte]

Amenorgamientu polinomial[editar | editar la fonte]

Artículu principal: Tresformamientu polinómica

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[editar | editar la fonte]

Artículu principal: NP-completu

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 llueñ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[editar | editar la fonte]

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ácticu, 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 non 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[editar | editar la fonte]

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[editar | editar la fonte]

Referencies[editar | editar la fonte]

  1. Richard M. Karp, "Combinatorics, Complexity, and Randomness", 1985 Turing Award Lecture.
  2. Richard M. Karp (1972), “Reducibility Among Combinatorial Problems”, in R. Y. Miller and J. W. Thatcher (editors), Complexity of Computer Computations, New York: Plenum, pp. 85–103 .
  3. Garey, Michael R., Johnson David S., (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, (page 4).
  4. Garey, Michael R., Johnson David S., (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, (page 8).
  5. 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).
  6. Garey, Michael R., Johnson David S., (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, (page 28).
  7. 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[editar | editar la fonte]

Llibros de testu[editar | editar la fonte]


Teoría de la complejidad computacional