fbpx
Wikipedia

Teoría de la complejidad computacional

La teoría de la complejidad computacional o teoría de la complejidad informática es una rama de la teoría de la computación que se centra en la clasificación de los problemas computacionales de acuerdo con su dificultad inherente, y en la relación entre dichas clases de complejidad.[1]

Un problema se cataloga como "inherentemente difícil" si su solución requiere de una cantidad significativa de recursos computacionales, sin importar el algoritmo utilizado. La teoría de la complejidad computacional formaliza dicha aseveración, introduciendo modelos de computación matemáticos para el estudio de estos problemas y la cuantificación de la cantidad de recursos necesarios para resolverlos, como tiempo y memoria.

Una de las metas de la teoría de la complejidad computacional es determinar los límites prácticos de qué es lo que se puede hacer en una computadora y qué no. Otros campos relacionados con la teoría de la complejidad computacional son el análisis de algoritmos y la teoría de la computabilidad. Una diferencia significativa entre el análisis de algoritmos y la teoría de la complejidad computacional, es que el primero se dedica a determinar la cantidad de recursos requeridos por un algoritmo en particular para resolver un problema, mientras que la segunda, analiza todos los posibles algoritmos que pudieran ser usados para resolver el mismo problema.

La teoría de la complejidad computacional trata de clasificar los problemas que pueden, o no pueden ser resueltos con una cantidad determinada de recursos. A su vez, la imposición de restricciones sobre estos recursos, es lo que la distingue de la teoría de la computabilidad, la cual se preocupa por qué tipo de problemas pueden ser resueltos de manera algorítmica.

Historia

Antes de que se realizaran investigaciones en torno a la complejidad de los algoritmos, se crearon los cimientos de esta teoría por varios investigadores. Uno de los aportes más influyentes fue la definición de las máquinas de Turing en 1936,[2]​ las cuales resultaron ser una noción de computadora muy flexible y robusta. A medida que las computadoras se desarrollaban en los 40's y los 50's, la Máquina de Turing demostró ser el modelo teórico correcto de cómputo.

Sin embargo, rápidamente se descubrió que el modelo básico de la máquina de Turing fallaba al cuantificar el tiempo y la memoria requerida por una computadora, un problema crítico hoy en día, y aún más en aquellos tiempos. La idea de medir el tiempo y espacio como una función de la longitud de la entrada se originó a principios de los 60s por Hartmanis y Stearns, y así nació la teoría de la complejidad computacional.

En los inicios, los investigadores trataban de entender las nuevas medidas de complejidad, y cómo se relacionaban unas con otras. En 1965, Edmonds definió un "buen" algoritmo como uno con un tiempo de ejecución acotado por un polinomio, es decir, con un tiempo de ejecución polinómico.[3]​ Esto condujo al surgimiento de uno de los conceptos más importantes de la teoría de la complejidad computacional: la NP-completitud y su pregunta fundamental, si P=NP.

El campo comenzó a florecer cuando el investigador estadounidense Stephen Cook y el soviético Leonid Levin, trabajando de manera independiente, probaron que existen problemas relevantes que son NP-completos. En 1972, Richard Karp llevó esta idea un paso más adelante, demostrando que 21 problemas combinatorios y de teoría de grafos, caracterizados por ser computacionalmente intratables, eran NP-completos.[4]​ También en los 70's, se produjo un crecimiento de las clases de complejidad a medida que los investigadores trataban de comprender los distintos modelos de cómputo existentes.

En los 80's, se produjo un auge de los modelos finitos, que analizaban el proceso de cómputo de una manera inherentemente distinta. Surgió un nuevo acercamiento a problemas como P=NP, y aun cuando estos modelos tenían sus limitaciones separando las clases de complejidad, esta aproximación introdujo técnicas combinatorias que permitieron un mejor entendimiento de los límites de estos modelos.

Ya en los 90's, se estudiaron nuevos modelos de cómputo como las computadoras cuánticas, donde una misma tarea puede tener diferente complejidad en la computación clásica y en la computación cuántica. Sin embargo, existen varias limitantes, entre ellas, la de desarrollar un hardware para este modelo, y que se requieren grandes cantidades de espacio para realizar los cálculos.

Problemas, algoritmos y complejidad

Para poder referirnos a problemas como "inherentemente intratables" y problemas de dificultad "equivalente", es necesario comprender algunos términos más básicos.[5]

Problema computacional

Un problema computacional constituye una pregunta a ser respondida, teniendo generalmente varios parámetros, o variables libres, cuyos valores no se han especificado. Un problema se describe mediante:

  1. Una descripción general de todos sus parámetros (pueden ser de entrada o de salida).
  2. Una sentencia que describa las propiedades que la respuesta, o la solución, debe cumplir.

Una instancia de un problema se obtiene cuando se especifican valores particulares para todos los parámetros del problema. Por ejemplo, consideremos el problema del test de primalidad. La instancia es un número (e.g. 15) y la solución es "sí" si el número es primo, y "no" en caso contrario. Visto de otra manera, la instancia es una entrada particular del problema, y la solución es la salida correspondiente para la entrada dada.

Problemas de decisión

Un problema de decisión es un tipo especial de problema computacional cuya respuesta es solamente "sí" o "no" (o, de manera más formal, "1" o "0").

Un problema de decisión pudiera verse como un lenguaje formal, donde los elementos que pertenecen al lenguaje son las instancias del problema cuya respuesta es "sí", los que no pertenecen al lenguaje son aquellas instancias cuya respuesta es "no". El objetivo es decidir, con la ayuda de un algoritmo, si una determinada entrada es un elemento del lenguaje formal considerado. Si el algoritmo devuelve como respuesta "sí", se dice que el algoritmo acepta la entrada, de lo contrario se dice que la rechaza.

Los problemas de decisión constituyen uno de los principales objetos de estudio de la teoría de la complejidad computacional, pues la NP-completitud se aplica directamente a estos tipos de problemas en vez de a problemas de optimización. Estos problemas tienen gran importancia porque casi todo problema puede transformarse en un problema de decisión.

Algoritmos

Podemos decir informalmente, que los algoritmos son procedimientos paso-a-paso para resolver problemas. Se puede pensar en ellos como simples programas de computadora, escritos en un lenguaje artificial específico.[6]

Se dice que un algoritmo resuelve un problema A, si dicho algoritmo se puede aplicar a cualquier instancia I de A, y se garantiza que siempre produce una solución para dicha instancia. De manera general, nos interesa encontrar el algoritmo más "eficiente" para resolver cierto problema. En su sentido más amplio, la noción de eficiencia involucra a todos los recursos computacionales necesarios para la ejecución de un algoritmo.

Por algoritmo "más eficiente" usualmente nos referimos al más rápido. Debido a que los requerimientos de tiempo son usualmente un factor dominante cuando se trata de determinar si un algoritmo es lo suficientemente eficiente para ser útil en la práctica, nos concentraremos en este recurso.

Algoritmos de tiempo polinómico y problemas intratables

Los científicos de la computación realizan la distinción entre algoritmos de Tiempo polinómico y algoritmos de tiempo exponencial cuando se trata de caracterizar a los algoritmos como "suficientemente eficiente" y "muy ineficiente" respectivamente.

Un algoritmo de tiempo polinomial se define como aquel con función de complejidad temporal dentro de una cota superior asintótica (denominada a veces "orden") O(p(n)) para alguna función polinómica p, donde n denota el tamaño de la entrada. Los algoritmos de tiempo exponencial,   son los que el número de ciclos que tienen que realizarse con el algoritmo es proporcional a la función   de modo que el poder computacional necesario para correr el algoritmo crece de forma exponencial al tamaño   del problema.

La mayoría de los algoritmos de tiempo exponencial son simples variaciones de una búsqueda exhaustiva, mientras que los algoritmos de tiempo polinomial, usualmente se obtienen mediante un análisis más profundo de la estructura del problema. En la teoría de la complejidad computacional, existe el consenso de que un problema no está "bien resuelto" hasta que se conozca un algoritmo de tiempo polinomial que lo resuelva. Por tanto, nos referiremos a un problema como intratable, si es tan difícil que no existe algoritmo de tiempo polinomial capaz de resolverlo.[7]

Clases de complejidad

Una clase de complejidad es un conjunto de problemas que poseen la misma complejidad computacional.

Definiendo clases de complejidad

Las clases de complejidad más sencillas se definen teniendo en cuenta factores como:

  • El tipo de problema computacional: Los problemas más comúnmente utilizados son los problemas de decisión, pero las clases de complejidad se pueden definir para otros tipos de problemas.
  • El modelo de cómputo: El modelo de cómputo más común es la Máquina de Turing determinista, pero muchas clases de complejidad se basan en Máquinas de Turing no deterministas, Máquinas de Turing cuánticas, etc.
  • El recurso (o recursos) que está(n) siendo acotado(s) y la(s) cota(s): Estas dos propiedades usualmente se utilizan juntas, por ejemplo, "tiempo polinomial", "espacio logarítmico", "profundidad constante", etc.

Máquinas de Turing deterministas y la clase P

La clase P contiene a aquellos problemas que son solubles en tiempo polinómico por una máquina de Turing determinista.[8]

Para la definición anterior se ha fijado el modelo de cómputo: la Máquina de Turing determinista. Existen distintas variantes de la Máquina de Turing y es conocido que la más débil de ellas puede simular a la más fuerte, adicionando a lo sumo un tiempo polinómico. En las décadas posteriores a la Tesis de Church-Turing surgieron otros modelos de cómputo, y se pudo mostrar que la Máquina de Turing también podía simularlos a lo sumo adicionando también un tiempo polinómico. Por tanto, la clase análoga a P para dichos modelos no es mayor que la clase P para el modelo de cómputo de la máquina de Turing.

La clase P juega un papel importante en la teoría de la complejidad computacional debido a que:

  1. P es invariante para todos los modelos de cómputo que son polinómica mente equivalentes a la Máquina de Turing determinista.
  2. A grandes rasgos, P corresponde a la clase de problemas que, de manera realista, son solubles en una computadora.

Computación no determinista y la clase NP

Muchas veces podemos evitar utilizar la fuerza bruta en los problemas para obtener soluciones en tiempo polinómico. Sin embargo, para algunos problemas esto no ha podido lograrse, es decir, no se conocen algoritmos que los resuelvan en tiempo polinómico. Quizás estos problemas tengan algoritmos en tiempo polinomial que se basan en principios por ahora desconocidos, o quizás estos problemas no pueden ser resueltos en tiempo polinómico, debido a que son "inherentemente difíciles".

La clase de complejidad NP consta de los problemas "verificables" en tiempo polinómico. Por verificable se entiende a un problema tal que dado un certificado de solución (candidato a solución), se puede verificar que dicho certificado es correcto en un tiempo polinómico en el tamaño de la entrada. A los problemas en la clase NP usualmente se les llama problemas NP.[9]

El término NP proviene de no determinista en tiempo polinómico y se deriva de un caracterización alternativa de esta clase, donde se utilizan Máquinas de Turing no deterministas. Informalmente, se puede definir la clase NP en términos de un algoritmo no determinista (recordar la equivalencia entre algoritmo y Máquina de Turing).

El algoritmo mencionado está compuesto por 2 etapas separadas. Dada una instancia del problema I, la primera etapa simplemente "adivina" un candidato a solución S. Entonces, la etapa de verificación recibe como entrada a I y a S, y procede a realizar el cómputo de una manera determinista, finalmente deteniéndose con la respuesta "sí", o con la respuesta "no", o sigue computando sin detenerse.

Al igual que la clase P, la clase NP es insensible a la elección del modelo de cómputo no determinista, debido a que dichos modelos son equivalentes polinómicamente.

Clases de complejidad importantes

Muchas clases de complejidad importantes pueden ser definidas acotando el tiempo o el espacio utilizado por el algoritmo. Algunas de estas clases de problemas de decisión son:

Clase de complejidad Modelo de cómputo Restricción de recurso
DTIME(f(n)) Máquina de Turing determinista Tiempo f(n)
P Máquina de Turing determinista Tiempo poly(n)
PP Máquina de Turing no determinista Tiempo poly(n)
EXPTIME Máquina de Turing determinista Tiempo 2poly(n)
NTIME(f(n)) Máquina de Turing no determinista Tiempo f(n)
NP Máquina de Turing no determinista Tiempo poly(n)
NEXPTIME Máquina de Turing no determinista Tiempo 2poly(n)
DSPACE(f(n)) Máquina de Turing determinista Espacio f(n)
L Máquina de Turing determinista Espacio O(log n)
PSPACE Máquina de Turing determinista Espacio poly(n)
EXPSPACE Máquina de Turing determinista Espacio 2poly(n)
NSPACE(f(n)) Máquina de Turing no determinista Espacio f(n)
NL Máquina de Turing no determinista Espacio O(log n)
NPSPACE Máquina de Turing no determinista Espacio poly(n)
NEXPSPACE Máquina de Turing no determinista Espacio 2poly(n)

La pregunta P=NP

La relación entre las clases P y NP es fundamental para la teoría de la NP-completitud. Intuitivamente, creemos que P es un subconjunto de NP. Y, efectivamente, cada problema de decisión resuelto por un algoritmo de tiempo polinomial determinista, también puede ser resuelto por un algoritmo de tiempo polinomial no determinista. Simplemente se necesita observar que cualquier algoritmo determinista puede ser utilizado en la etapa de verificación de un algoritmo no determinista. Si B es un problema de P, y A es un algoritmo de tiempo polinomial para B, entonces se puede construir un algoritmo de tiempo polinomial no determinista para B, simplemente utilizando A en la etapa de verificación e ignorando la etapa de adivinación. Por tanto, si B pertenece a P, entonces B también pertenece a NP.

La pregunta P=NP es una de las más importantes en el campo de las ciencias de la computación, debido a las grandes repercusiones que habría, en caso de encontrarse una solución. Si P=NP, cualquier problema polinómica mente verificable sería polinómica mente decidible. La mayoría de los investigadores cree que estas clases no son iguales, porque se ha realizado bastantes esfuerzos, sin éxito, para encontrar algoritmos de tiempo polinomial para varios problemas en NP. Los investigadores también han tratado de probar que las clases son distintas, pero eso conllevaría a mostrar que no existe un algoritmo «eficiente» para reemplazar a la búsqueda por fuerza bruta.

NP-Completitud

Reducción polinomial

Una reducción es una transformación de un problema en otro problema. Intuitivamente, un problema Q puede ser reducido a otro problema Q', si cualquier instancia del problema Q puede ser "fácilmente" expresada como una instancia del problema Q', y cuya solución proporcione una solución para la instancia de Q.[10]

Existen muchos tipos de reducciones: basadas en el método de reducción, como las reducciones de Cook, las reducciones de Karp y las reducciones de Levin, y las basadas en la cota de la complejidad, como la reducción en tiempo polinomial o la reducción de espacio logarítmica. Una de las reducciones más utilizadas es la reducción en tiempo polinomial, lo cual significa que el proceso de reducción toma un tiempo polinomial.

Problemas NP-completos

Las reducciones en tiempo polinomial nos dotan de elementos para probar, de una manera formal, que un problema es al menos tan difícil que otro, con una diferencia de un factor polinomial. Estas son esenciales para definir a los problemas NP-completos, además de ayudar a comprender los mismos.

La clase de los problemas NP-completos contiene a los problemas más difíciles en NP, en el sentido de que son los que estén más lejos de estar en P. Debido a que el problema P=NP no ha sido resuelto, el hecho de reducir un problema B, a otro problema A, indicaría que no se conoce solución en tiempo polinomial para A. Esto es debido a que una solución en tiempo polinomial para A, tendría como consecuencia la existencia de una solución polinomial para B. De manera similar, debido a que todos los problemas NP pueden ser reducidos a este conjunto, encontrar un problema NP-completo que pueda ser resuelto en un tiempo polinomial significaría que P=NP.

Importancia de la NP-Completitud

Quizás la razón de mayor peso por la cual los científicos de la computación creen que P es distinto de NP, es la existencia de la clase de problemas "NP-completos". Esta clase tiene la curiosa propiedad de que si algún problema NP-completo puede ser resuelto en tiempo polinomial, entonces todo problema en NP tiene una solución en tiempo polinomial, es decir, P=NP. A pesar de años de estudio, ningún algoritmo de tiempo polinomial se ha descubierto para ningún problema NP-completo.

Desde el punto de vista teórico, un investigador intentando mostrar que la clase P es distinta de la clase NP, pudiera enfocarse en un problema NP-completo. Si algún problema en NP requiere más que un tiempo polinomial, entonces uno NP-completo también. Además, un investigador intentando demostrar que P=NP, solo necesita encontrar un algoritmo de tiempo polinomial para un problema NP-completo para lograrlo.

Desde el punto de vista práctico, el fenómeno de la NP-completitud puede prevenir la pérdida de tiempo cuando se busca un algoritmo de tiempo polinomial no existente para resolver un problema determinado. Aun cuando no se posean los elementos matemáticos para demostrar que cierto problema no se puede resolver en tiempo polinomial, creemos que P no es igual a NP, así que demostrar que el problema es NP-completo, es una fuerte evidencia de su no "polinomialdad".

Haciendo frente a problemas NP

Teniendo en cuenta la definición de problema intratable, si no se cumple que P=NP, entonces los problemas NP-completos son intratables.

Muchos problemas de la práctica son NP-completos, y son muy importantes como para desistir simplemente porque no sabemos cómo encontrar una solución óptima en tiempo polinomial. Aunque un problema sea NP-completo, puede haber esperanza. Existen tres estrategias fundamentales para lidiar con un problema NP-completo:

  • Si la entrada es pequeña, un algoritmo con tiempo de ejecución exponencial pudiera ser perfectamente aceptable.
  • Se pudieran aislar algunos casos especiales que se pudieran resolver en tiempo polinomial.
  • Podríamos utilizar aproximaciones para encontrar soluciones lo suficientemente cercanas al óptimo en tiempo polinomial. En la práctica, obtener soluciones cercanas al óptimo es bastante aceptable. A estos algoritmos se les denomina algoritmos de aproximación, y en muchos casos se apoyan en heurísticas y metaheurísticas.

Véase también

Referencias

  1. Dean, Walter (2016). «Computational Complexity Theory». The Stanford Encyclopedia of Philosophy (en inglés). Metaphysics Research Lab, Stanford University. 
  2. Senen Barro, Ameneiro (2002). «1». Fronteras de la computación (2 edición). Diaz de Santos. p. 11. ISBN 9788479785178. 
  3. Richard M. Karp, "Combinatorics, Complexity, and Randomness", 1985 Turing Award Lecture.
  4. Richard M. Karp (1972), «Reducibility Among Combinatorial Problems», en R. E. Miller and J. W. Thatcher (editors), ed., Complexity of Computer Computations, New York: Plenum, pp. 85-103 ..
  5. García Merayo, Félix (2015). «11.3». Matemática discreta (3 edición). Ediciones Paraninfo, S.A. p. 548. ISBN 978-84-283-3568-3. 
  6. Garey, Michael R., Johnson David S., (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, (page 4).
  7. Garey, Michael R., Johnson David S., (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, (page 8).
  8. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. & Stein, Clifford, (2010), Introduction to Algorithms, 3.ª edición, MIT Press and McGraw-Hill, (page 1049).
  9. Garey, Michael R., Johnson David S., (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, (page 28).
  10. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. & Stein, Clifford, (2010), Introduction to Algorithms, 3.ª edición, MIT Press and McGraw-Hill, (page 1067).

Artículos

  • Cook, Stephen (1983), «An overview of computational complexity», Commun. ACM (ACM) 26 (6): 400-408, ISSN 0001-0782 .
  • Fortnow, Lance; Homer, Steven (2002), «A Short History of Computational Complexity», Bulletin of the EATCS 80: 95-133 .

Libros de texto

  • Sipser, Michael (2006), Introduction to the Theory of Computation (2da edición), USA: Thomson Course Technology, ISBN 0-534-95097-3 .
  •   Datos: Q205084
  •   Multimedia: Computational complexity theory

teoría, complejidad, computacional, este, artículo, detectaron, varios, problemas, favor, edítalo, para, mejorarlo, necesita, referencias, adicionales, para, verificación, requiere, revisión, ortográfica, gramatical, puedes, avisar, redactor, principal, pegand. En este articulo se detectaron varios problemas Por favor editalo para mejorarlo Necesita referencias adicionales para su verificacion Requiere una revision ortografica y gramatical Puedes avisar al redactor principal pegando lo siguiente en su pagina de discusion sust Aviso PA Teoria de la complejidad computacional copyedit referencias adicionales La teoria de la complejidad computacional o teoria de la complejidad informatica es una rama de la teoria de la computacion que se centra en la clasificacion de los problemas computacionales de acuerdo con su dificultad inherente y en la relacion entre dichas clases de complejidad 1 Un problema se cataloga como inherentemente dificil si su solucion requiere de una cantidad significativa de recursos computacionales sin importar el algoritmo utilizado La teoria de la complejidad computacional formaliza dicha aseveracion introduciendo modelos de computacion matematicos para el estudio de estos problemas y la cuantificacion de la cantidad de recursos necesarios para resolverlos como tiempo y memoria Una de las metas de la teoria de la complejidad computacional es determinar los limites practicos de que es lo que se puede hacer en una computadora y que no Otros campos relacionados con la teoria de la complejidad computacional son el analisis de algoritmos y la teoria de la computabilidad Una diferencia significativa entre el analisis de algoritmos y la teoria de la complejidad computacional es que el primero se dedica a determinar la cantidad de recursos requeridos por un algoritmo en particular para resolver un problema mientras que la segunda analiza todos los posibles algoritmos que pudieran ser usados para resolver el mismo problema La teoria de la complejidad computacional trata de clasificar los problemas que pueden o no pueden ser resueltos con una cantidad determinada de recursos A su vez la imposicion de restricciones sobre estos recursos es lo que la distingue de la teoria de la computabilidad la cual se preocupa por que tipo de problemas pueden ser resueltos de manera algoritmica Indice 1 Historia 2 Problemas algoritmos y complejidad 2 1 Problema computacional 2 2 Problemas de decision 2 3 Algoritmos 2 4 Algoritmos de tiempo polinomico y problemas intratables 3 Clases de complejidad 3 1 Definiendo clases de complejidad 3 2 Maquinas de Turing deterministas y la clase P 3 3 Computacion no determinista y la clase NP 3 4 Clases de complejidad importantes 4 La pregunta P NP 5 NP Completitud 5 1 Reduccion polinomial 5 2 Problemas NP completos 5 3 Importancia de la NP Completitud 6 Haciendo frente a problemas NP 7 Vease tambien 8 Referencias 8 1 Articulos 8 2 Libros de textoHistoria EditarAntes de que se realizaran investigaciones en torno a la complejidad de los algoritmos se crearon los cimientos de esta teoria por varios investigadores Uno de los aportes mas influyentes fue la definicion de las maquinas de Turing en 1936 2 las cuales resultaron ser una nocion de computadora muy flexible y robusta A medida que las computadoras se desarrollaban en los 40 s y los 50 s la Maquina de Turing demostro ser el modelo teorico correcto de computo Sin embargo rapidamente se descubrio que el modelo basico de la maquina de Turing fallaba al cuantificar el tiempo y la memoria requerida por una computadora un problema critico hoy en dia y aun mas en aquellos tiempos La idea de medir el tiempo y espacio como una funcion de la longitud de la entrada se origino a principios de los 60s por Hartmanis y Stearns y asi nacio la teoria de la complejidad computacional En los inicios los investigadores trataban de entender las nuevas medidas de complejidad y como se relacionaban unas con otras En 1965 Edmonds definio un buen algoritmo como uno con un tiempo de ejecucion acotado por un polinomio es decir con un tiempo de ejecucion polinomico 3 Esto condujo al surgimiento de uno de los conceptos mas importantes de la teoria de la complejidad computacional la NP completitud y su pregunta fundamental si P NP El campo comenzo a florecer cuando el investigador estadounidense Stephen Cook y el sovietico Leonid Levin trabajando de manera independiente probaron que existen problemas relevantes que son NP completos En 1972 Richard Karp llevo esta idea un paso mas adelante demostrando que 21 problemas combinatorios y de teoria de grafos caracterizados por ser computacionalmente intratables eran NP completos 4 Tambien en los 70 s se produjo un crecimiento de las clases de complejidad a medida que los investigadores trataban de comprender los distintos modelos de computo existentes En los 80 s se produjo un auge de los modelos finitos que analizaban el proceso de computo de una manera inherentemente distinta Surgio un nuevo acercamiento a problemas como P NP y aun cuando estos modelos tenian sus limitaciones separando las clases de complejidad esta aproximacion introdujo tecnicas combinatorias que permitieron un mejor entendimiento de los limites de estos modelos Ya en los 90 s se estudiaron nuevos modelos de computo como las computadoras cuanticas donde una misma tarea puede tener diferente complejidad en la computacion clasica y en la computacion cuantica Sin embargo existen varias limitantes entre ellas la de desarrollar un hardware para este modelo y que se requieren grandes cantidades de espacio para realizar los calculos Problemas algoritmos y complejidad EditarPara poder referirnos a problemas como inherentemente intratables y problemas de dificultad equivalente es necesario comprender algunos terminos mas basicos 5 Problema computacional Editar Articulo principal Problema computacional Un problema computacional constituye una pregunta a ser respondida teniendo generalmente varios parametros o variables libres cuyos valores no se han especificado Un problema se describe mediante Una descripcion general de todos sus parametros pueden ser de entrada o de salida Una sentencia que describa las propiedades que la respuesta o la solucion debe cumplir Una instancia de un problema se obtiene cuando se especifican valores particulares para todos los parametros del problema Por ejemplo consideremos el problema del test de primalidad La instancia es un numero e g 15 y la solucion es si si el numero es primo y no en caso contrario Visto de otra manera la instancia es una entrada particular del problema y la solucion es la salida correspondiente para la entrada dada Problemas de decision Editar Articulo principal Problema de decision Un problema de decision es un tipo especial de problema computacional cuya respuesta es solamente si o no o de manera mas formal 1 o 0 Un problema de decision pudiera verse como un lenguaje formal donde los elementos que pertenecen al lenguaje son las instancias del problema cuya respuesta es si los que no pertenecen al lenguaje son aquellas instancias cuya respuesta es no El objetivo es decidir con la ayuda de un algoritmo si una determinada entrada es un elemento del lenguaje formal considerado Si el algoritmo devuelve como respuesta si se dice que el algoritmo acepta la entrada de lo contrario se dice que la rechaza Los problemas de decision constituyen uno de los principales objetos de estudio de la teoria de la complejidad computacional pues la NP completitud se aplica directamente a estos tipos de problemas en vez de a problemas de optimizacion Estos problemas tienen gran importancia porque casi todo problema puede transformarse en un problema de decision Algoritmos Editar Articulo principal Algoritmo Podemos decir informalmente que los algoritmos son procedimientos paso a paso para resolver problemas Se puede pensar en ellos como simples programas de computadora escritos en un lenguaje artificial especifico 6 Se dice que un algoritmo resuelve un problema A si dicho algoritmo se puede aplicar a cualquier instancia I de A y se garantiza que siempre produce una solucion para dicha instancia De manera general nos interesa encontrar el algoritmo mas eficiente para resolver cierto problema En su sentido mas amplio la nocion de eficiencia involucra a todos los recursos computacionales necesarios para la ejecucion de un algoritmo Por algoritmo mas eficiente usualmente nos referimos al mas rapido Debido a que los requerimientos de tiempo son usualmente un factor dominante cuando se trata de determinar si un algoritmo es lo suficientemente eficiente para ser util en la practica nos concentraremos en este recurso Algoritmos de tiempo polinomico y problemas intratables Editar Los cientificos de la computacion realizan la distincion entre algoritmos de Tiempo polinomico y algoritmos de tiempo exponencial cuando se trata de caracterizar a los algoritmos como suficientemente eficiente y muy ineficiente respectivamente Un algoritmo de tiempo polinomial se define como aquel con funcion de complejidad temporal dentro de una cota superior asintotica denominada a veces orden O p n para alguna funcion polinomica p donde n denota el tamano de la entrada Los algoritmos de tiempo exponencial O e n displaystyle O e n son los que el numero de ciclos que tienen que realizarse con el algoritmo es proporcional a la funcion e n displaystyle e n de modo que el poder computacional necesario para correr el algoritmo crece de forma exponencial al tamano n displaystyle n del problema La mayoria de los algoritmos de tiempo exponencial son simples variaciones de una busqueda exhaustiva mientras que los algoritmos de tiempo polinomial usualmente se obtienen mediante un analisis mas profundo de la estructura del problema En la teoria de la complejidad computacional existe el consenso de que un problema no esta bien resuelto hasta que se conozca un algoritmo de tiempo polinomial que lo resuelva Por tanto nos referiremos a un problema como intratable si es tan dificil que no existe algoritmo de tiempo polinomial capaz de resolverlo 7 Clases de complejidad EditarArticulo principal Clase de complejidad Una clase de complejidad es un conjunto de problemas que poseen la misma complejidad computacional Definiendo clases de complejidad Editar Las clases de complejidad mas sencillas se definen teniendo en cuenta factores como El tipo de problema computacional Los problemas mas comunmente utilizados son los problemas de decision pero las clases de complejidad se pueden definir para otros tipos de problemas El modelo de computo El modelo de computo mas comun es la Maquina de Turing determinista pero muchas clases de complejidad se basan en Maquinas de Turing no deterministas Maquinas de Turing cuanticas etc El recurso o recursos que esta n siendo acotado s y la s cota s Estas dos propiedades usualmente se utilizan juntas por ejemplo tiempo polinomial espacio logaritmico profundidad constante etc Maquinas de Turing deterministas y la clase P Editar Articulo principal P clase de complejidad La clase P contiene a aquellos problemas que son solubles en tiempo polinomico por una maquina de Turing determinista 8 Para la definicion anterior se ha fijado el modelo de computo la Maquina de Turing determinista Existen distintas variantes de la Maquina de Turing y es conocido que la mas debil de ellas puede simular a la mas fuerte adicionando a lo sumo un tiempo polinomico En las decadas posteriores a la Tesis de Church Turing surgieron otros modelos de computo y se pudo mostrar que la Maquina de Turing tambien podia simularlos a lo sumo adicionando tambien un tiempo polinomico Por tanto la clase analoga a P para dichos modelos no es mayor que la clase P para el modelo de computo de la maquina de Turing La clase P juega un papel importante en la teoria de la complejidad computacional debido a que P es invariante para todos los modelos de computo que son polinomica mente equivalentes a la Maquina de Turing determinista A grandes rasgos P corresponde a la clase de problemas que de manera realista son solubles en una computadora Computacion no determinista y la clase NP Editar Articulo principal NP clase de complejidad Muchas veces podemos evitar utilizar la fuerza bruta en los problemas para obtener soluciones en tiempo polinomico Sin embargo para algunos problemas esto no ha podido lograrse es decir no se conocen algoritmos que los resuelvan en tiempo polinomico Quizas estos problemas tengan algoritmos en tiempo polinomial que se basan en principios por ahora desconocidos o quizas estos problemas no pueden ser resueltos en tiempo polinomico debido a que son inherentemente dificiles La clase de complejidad NP consta de los problemas verificables en tiempo polinomico Por verificable se entiende a un problema tal que dado un certificado de solucion candidato a solucion se puede verificar que dicho certificado es correcto en un tiempo polinomico en el tamano de la entrada A los problemas en la clase NP usualmente se les llama problemas NP 9 El termino NP proviene de no determinista en tiempo polinomico y se deriva de un caracterizacion alternativa de esta clase donde se utilizan Maquinas de Turing no deterministas Informalmente se puede definir la clase NP en terminos de un algoritmo no determinista recordar la equivalencia entre algoritmo y Maquina de Turing El algoritmo mencionado esta compuesto por 2 etapas separadas Dada una instancia del problema I la primera etapa simplemente adivina un candidato a solucion S Entonces la etapa de verificacion recibe como entrada a I y a S y procede a realizar el computo de una manera determinista finalmente deteniendose con la respuesta si o con la respuesta no o sigue computando sin detenerse Al igual que la clase P la clase NP es insensible a la eleccion del modelo de computo no determinista debido a que dichos modelos son equivalentes polinomicamente Clases de complejidad importantes Editar Muchas clases de complejidad importantes pueden ser definidas acotando el tiempo o el espacio utilizado por el algoritmo Algunas de estas clases de problemas de decision son Clase de complejidad Modelo de computo Restriccion de recursoDTIME f n Maquina de Turing determinista Tiempo f n P Maquina de Turing determinista Tiempo poly n PP Maquina de Turing no determinista Tiempo poly n EXPTIME Maquina de Turing determinista Tiempo 2poly n NTIME f n Maquina de Turing no determinista Tiempo f n NP Maquina de Turing no determinista Tiempo poly n NEXPTIME Maquina de Turing no determinista Tiempo 2poly n DSPACE f n Maquina de Turing determinista Espacio f n L Maquina de Turing determinista Espacio O log n PSPACE Maquina de Turing determinista Espacio poly n EXPSPACE Maquina de Turing determinista Espacio 2poly n NSPACE f n Maquina de Turing no determinista Espacio f n NL Maquina de Turing no determinista Espacio O log n NPSPACE Maquina de Turing no determinista Espacio poly n NEXPSPACE Maquina de Turing no determinista Espacio 2poly n La pregunta P NP EditarArticulo principal Clases de complejidad P y NP La relacion entre las clases P y NP es fundamental para la teoria de la NP completitud Intuitivamente creemos que P es un subconjunto de NP Y efectivamente cada problema de decision resuelto por un algoritmo de tiempo polinomial determinista tambien puede ser resuelto por un algoritmo de tiempo polinomial no determinista Simplemente se necesita observar que cualquier algoritmo determinista puede ser utilizado en la etapa de verificacion de un algoritmo no determinista Si B es un problema de P y A es un algoritmo de tiempo polinomial para B entonces se puede construir un algoritmo de tiempo polinomial no determinista para B simplemente utilizando A en la etapa de verificacion e ignorando la etapa de adivinacion Por tanto si B pertenece a P entonces B tambien pertenece a NP La pregunta P NP es una de las mas importantes en el campo de las ciencias de la computacion debido a las grandes repercusiones que habria en caso de encontrarse una solucion Si P NP cualquier problema polinomica mente verificable seria polinomica mente decidible La mayoria de los investigadores cree que estas clases no son iguales porque se ha realizado bastantes esfuerzos sin exito para encontrar algoritmos de tiempo polinomial para varios problemas en NP Los investigadores tambien han tratado de probar que las clases son distintas pero eso conllevaria a mostrar que no existe un algoritmo eficiente para reemplazar a la busqueda por fuerza bruta NP Completitud EditarReduccion polinomial Editar Articulo principal Transformacion polinomica Una reduccion es una transformacion de un problema en otro problema Intuitivamente un problema Q puede ser reducido a otro problema Q si cualquier instancia del problema Q puede ser facilmente expresada como una instancia del problema Q y cuya solucion proporcione una solucion para la instancia de Q 10 Existen muchos tipos de reducciones basadas en el metodo de reduccion como las reducciones de Cook las reducciones de Karp y las reducciones de Levin y las basadas en la cota de la complejidad como la reduccion en tiempo polinomial o la reduccion de espacio logaritmica Una de las reducciones mas utilizadas es la reduccion en tiempo polinomial lo cual significa que el proceso de reduccion toma un tiempo polinomial Problemas NP completos Editar Articulo principal NP completo Las reducciones en tiempo polinomial nos dotan de elementos para probar de una manera formal que un problema es al menos tan dificil que otro con una diferencia de un factor polinomial Estas son esenciales para definir a los problemas NP completos ademas de ayudar a comprender los mismos La clase de los problemas NP completos contiene a los problemas mas dificiles en NP en el sentido de que son los que esten mas lejos de estar en P Debido a que el problema P NP no ha sido resuelto el hecho de reducir un problema B a otro problema A indicaria que no se conoce solucion en tiempo polinomial para A Esto es debido a que una solucion en tiempo polinomial para A tendria como consecuencia la existencia de una solucion polinomial para B De manera similar debido a que todos los problemas NP pueden ser reducidos a este conjunto encontrar un problema NP completo que pueda ser resuelto en un tiempo polinomial significaria que P NP Importancia de la NP Completitud Editar Quizas la razon de mayor peso por la cual los cientificos de la computacion creen que P es distinto de NP es la existencia de la clase de problemas NP completos Esta clase tiene la curiosa propiedad de que si algun problema NP completo puede ser resuelto en tiempo polinomial entonces todo problema en NP tiene una solucion en tiempo polinomial es decir P NP A pesar de anos de estudio ningun algoritmo de tiempo polinomial se ha descubierto para ningun problema NP completo Desde el punto de vista teorico un investigador intentando mostrar que la clase P es distinta de la clase NP pudiera enfocarse en un problema NP completo Si algun problema en NP requiere mas que un tiempo polinomial entonces uno NP completo tambien Ademas un investigador intentando demostrar que P NP solo necesita encontrar un algoritmo de tiempo polinomial para un problema NP completo para lograrlo Desde el punto de vista practico el fenomeno de la NP completitud puede prevenir la perdida de tiempo cuando se busca un algoritmo de tiempo polinomial no existente para resolver un problema determinado Aun cuando no se posean los elementos matematicos para demostrar que cierto problema no se puede resolver en tiempo polinomial creemos que P no es igual a NP asi que demostrar que el problema es NP completo es una fuerte evidencia de su no polinomialdad Haciendo frente a problemas NP EditarTeniendo en cuenta la definicion de problema intratable si no se cumple que P NP entonces los problemas NP completos son intratables Muchos problemas de la practica son NP completos y son muy importantes como para desistir simplemente porque no sabemos como encontrar una solucion optima en tiempo polinomial Aunque un problema sea NP completo puede haber esperanza Existen tres estrategias fundamentales para lidiar con un problema NP completo Si la entrada es pequena un algoritmo con tiempo de ejecucion exponencial pudiera ser perfectamente aceptable Se pudieran aislar algunos casos especiales que se pudieran resolver en tiempo polinomial Podriamos utilizar aproximaciones para encontrar soluciones lo suficientemente cercanas al optimo en tiempo polinomial En la practica obtener soluciones cercanas al optimo es bastante aceptable A estos algoritmos se les denomina algoritmos de aproximacion y en muchos casos se apoyan en heuristicas y metaheuristicas Vease tambien EditarReduccion complejidad Teorema de Cook Levin Lista de 21 problemas NP completos de Karp Clases de complejidad P y NP Teorema de la jerarquia temporal Anexo Clases de complejidad Complejidad de KolmogorovReferencias Editar Dean Walter 2016 Computational Complexity Theory The Stanford Encyclopedia of Philosophy en ingles Metaphysics Research Lab Stanford University Senen Barro Ameneiro 2002 1 Fronteras de la computacion 2 edicion Diaz de Santos p 11 ISBN 9788479785178 Richard M Karp Combinatorics Complexity and Randomness 1985 Turing Award Lecture Richard M Karp 1972 Reducibility Among Combinatorial Problems en R E Miller and J W Thatcher editors ed Complexity of Computer Computations New York Plenum pp 85 103 Garcia Merayo Felix 2015 11 3 Matematica discreta 3 edicion Ediciones Paraninfo S A p 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 Cormen Thomas H Leiserson Charles E Rivest Ronald L amp Stein Clifford 2010 Introduction to Algorithms 3 ª edicion 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 E Rivest Ronald L amp Stein Clifford 2010 Introduction to Algorithms 3 ª edicion MIT Press and McGraw Hill page 1067 Articulos Editar Cook Stephen 1983 An overview of computational complexity Commun ACM ACM 26 6 400 408 ISSN 0001 0782 Fortnow Lance Homer Steven 2002 A Short History of Computational Complexity Bulletin of the EATCS 80 95 133 Libros de texto Editar Arora Sanjeev Barak Boaz 2009 Computational Complexity A Modern Approach Cambridge ISBN 978 0 521 42426 4 Zbl 1193 68112 Sipser Michael 2006 Introduction to the Theory of Computation 2da edicion 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 E Rivest Ronald L amp Stein Clifford 2010 Introduction to Algorithms 3ra edicion Cambridge MA MIT Press and McGraw Hill ISBN 0 262 03384 4 Datos Q205084 Multimedia Computational complexity theory Obtenido de https es wikipedia org w index php title Teoria de la complejidad computacional amp oldid 131736491, wikipedia, wiki, leyendo, leer, libro, biblioteca,

español

, española, descargar, gratis, descargar gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, imagen, música, canción, película, libro, juego, juegos