Complejidad - Complexity

Para su uso en ciencias de la computación, consulte Complejidad computacional . Para otros usos, consulte Complejidad (desambiguación) .

La complejidad caracteriza el comportamiento de un sistema o modelo cuyos componentes interactúan de múltiples formas y siguen reglas locales, lo que significa que no existe una instrucción superior razonable para definir las diversas interacciones posibles.

El término se usa generalmente para caracterizar algo con muchas partes donde esas partes interactúan entre sí de múltiples maneras, culminando en un orden de emergencia superior a la suma de sus partes. El estudio de estos vínculos complejos a varias escalas es el objetivo principal de la teoría de sistemas complejos .

La ciencia a partir de 2010 adopta una serie de enfoques para caracterizar la complejidad; Zayed y col. reflejan muchos de estos. Neil Johnson afirma que "incluso entre los científicos, no existe una definición única de complejidad, y la noción científica se ha transmitido tradicionalmente utilizando ejemplos particulares ..." En última instancia, Johnson adopta la definición de "ciencia de la complejidad" como "el estudio de los fenómenos que emergen de una colección de objetos que interactúan ".

Visión general

Las definiciones de complejidad a menudo dependen del concepto de " sistema ", un conjunto de partes o elementos que tienen relaciones entre ellos diferenciadas de las relaciones con otros elementos fuera del régimen relacional. Muchas definiciones tienden a postular o asumir que la complejidad expresa una condición de numerosos elementos en un sistema y numerosas formas de relaciones entre los elementos. Sin embargo, lo que uno ve como complejo y lo que uno ve como simple es relativo y cambia con el tiempo.

Warren Weaver postuló en 1948 dos formas de complejidad: complejidad desorganizada y complejidad organizada. Los fenómenos de 'complejidad desorganizada' se tratan utilizando la teoría de la probabilidad y la mecánica estadística, mientras que la 'complejidad organizada' se ocupa de fenómenos que escapan a tales enfoques y confrontan "tratar simultáneamente con un número considerable de factores que están interrelacionados en un todo orgánico". El artículo de Weaver de 1948 ha influido en el pensamiento posterior sobre la complejidad.

Los enfoques que incorporan conceptos de sistemas, elementos múltiples, regímenes relacionales múltiples y espacios de estados pueden resumirse como implicando que la complejidad surge del número de regímenes relacionales distinguibles (y sus espacios de estados asociados) en un sistema definido.

Algunas definiciones se relacionan con la base algorítmica para la expresión de un fenómeno o modelo complejo o expresión matemática, como se establece más adelante en este documento.

Desorganizado vs. organizado

Uno de los problemas al abordar cuestiones de complejidad ha sido formalizar la distinción conceptual intuitiva entre la gran cantidad de variaciones en las relaciones existentes en colecciones aleatorias, y el número a veces grande, pero menor, de relaciones entre elementos en sistemas donde las restricciones (relacionadas con la correlación de elementos independientes de otro modo) reducen simultáneamente las variaciones de la independencia de los elementos y crean regímenes distinguibles de relaciones o interacciones más uniformes o correlacionadas.

Weaver percibió y abordó este problema, al menos de manera preliminar, al establecer una distinción entre "complejidad desorganizada" y "complejidad organizada".

En opinión de Weaver, la complejidad desorganizada resulta de que el sistema particular tiene una gran cantidad de partes, digamos millones de partes, o muchas más. Aunque las interacciones de las partes en una situación de "complejidad desorganizada" pueden verse como en gran parte aleatorias, las propiedades del sistema en su conjunto pueden entenderse utilizando métodos de probabilidad y estadísticos.

Un excelente ejemplo de complejidad desorganizada es un gas en un recipiente, con las moléculas de gas como partes. Algunos sugerirían que un sistema de complejidad desorganizada puede compararse con la (relativa) simplicidad de las órbitas planetarias; esta última puede predecirse aplicando las leyes del movimiento de Newton . Por supuesto, la mayoría de los sistemas del mundo real, incluidas las órbitas planetarias, eventualmente se vuelven teóricamente impredecibles incluso usando la dinámica newtoniana; según lo descubierto por la teoría del caos moderna .

La complejidad organizada, en opinión de Weaver, no reside en nada más que la interacción no aleatoria o correlacionada entre las partes. Estas relaciones correlacionadas crean una estructura diferenciada que puede, como sistema, interactuar con otros sistemas. El sistema coordinado manifiesta propiedades que no son transmitidas o dictadas por partes individuales. Se puede decir que el aspecto organizado de esta forma de complejidad frente a otros sistemas distintos del sistema sujeto "emerge", sin ninguna "mano guía".

No es necesario que el número de piezas sea muy grande para que un sistema en particular tenga propiedades emergentes. Un sistema de complejidad organizada puede entenderse en sus propiedades (comportamiento entre las propiedades) mediante el modelado y la simulación , en particular el modelado y la simulación con computadoras . Un ejemplo de complejidad organizada es un barrio de la ciudad como mecanismo de vida, con la gente del barrio entre las partes del sistema.

Fuentes y factores

Generalmente existen reglas que pueden invocarse para explicar el origen de la complejidad en un sistema dado.

La fuente de la complejidad desorganizada es la gran cantidad de partes del sistema de interés y la falta de correlación entre los elementos del sistema.

En el caso de los sistemas vivos autoorganizados, la complejidad organizada de manera útil proviene de organismos benéficamente mutados que son seleccionados para sobrevivir por su entorno por su capacidad reproductiva diferencial o al menos por el éxito sobre la materia inanimada o los organismos complejos menos organizados. Véase, por ejemplo , el tratamiento de los ecosistemas por Robert Ulanowicz .

La complejidad de un objeto o sistema es una propiedad relativa. Por ejemplo, para muchas funciones (problemas), una complejidad computacional como el tiempo de cálculo es menor cuando se utilizan máquinas de Turing de varias cintas que cuando se utilizan máquinas de Turing con una cinta. Las máquinas de acceso aleatorio permiten disminuir aún más la complejidad del tiempo (Greenlaw y Hoover 1998: 226), mientras que las máquinas de Turing inductivas pueden disminuir incluso la clase de complejidad de una función, lenguaje o conjunto (Burgin 2005). Esto muestra que las herramientas de actividad pueden ser un factor importante de complejidad.

Significados variados

En varios campos científicos, "complejidad" tiene un significado preciso:

  • En la teoría de la complejidad computacional se estudia la cantidad de recursos necesarios para la ejecución de algoritmos . Los tipos más populares de complejidad computacional son la complejidad temporal de un problema igual al número de pasos que se necesitan para resolver una instancia del problema en función del tamaño de la entrada (generalmente medido en bits), utilizando el método más eficiente algoritmo, y la complejidad espacial de un problema igual al volumen de la memoria utilizada por el algoritmo (por ejemplo, celdas de la cinta) que se necesita para resolver una instancia del problema en función del tamaño de la entrada (generalmente medido en bits), utilizando el algoritmo más eficiente. Esto permite la clasificación de problemas computacionales por clase de complejidad (como P , NP , etc.). Manuel Blum desarrolló un enfoque axiomático de la complejidad computacional . Permite deducir muchas propiedades de medidas concretas de complejidad computacional, como la complejidad del tiempo o la complejidad del espacio, a partir de propiedades de medidas definidas axiomáticamente.
  • En la teoría de la información algorítmica , la complejidad de Kolmogorov (también llamada complejidad descriptiva , complejidad algorítmica o entropía algorítmica ) de una cadena es la longitud del programa binario más corto que genera esa cadena. La longitud mínima del mensaje es una aplicación práctica de este enfoque. Se estudian diferentes tipos de complejidad de Kolmogorov: la complejidad uniforme, la complejidad del prefijo, la complejidad monótona, la complejidad de Kolmogorov limitada en el tiempo y la complejidad de Kolmogorov limitada por el espacio. Mark Burgin introdujo un enfoque axiomático de la complejidad de Kolmogorov basado en los axiomas de Blum (Blum 1967) en el artículo presentado para su publicación por Andrey Kolmogorov . El enfoque axiomático abarca otros enfoques de la complejidad de Kolmogorov. Es posible tratar diferentes tipos de complejidad de Kolmogorov como casos particulares de complejidad de Kolmogorov generalizada definida axiomáticamente. En lugar de probar teoremas similares, como el teorema de invariancia básico, para cada medida particular, es posible deducir fácilmente todos esos resultados a partir de un teorema correspondiente probado en el escenario axiomático. Ésta es una ventaja general del enfoque axiomático en matemáticas. El enfoque axiomático de la complejidad de Kolmogorov se desarrolló más en el libro (Burgin 2005) y se aplicó a las métricas de software (Burgin y Debnath, 2003; Debnath y Burgin, 2003).
  • En la teoría de la información , la complejidad de la fluctuación de la información es la fluctuación de la información sobre la entropía de la información . Se deriva de las fluctuaciones en el predominio del orden y el caos en un sistema dinámico y se ha utilizado como medida de complejidad en muchos campos diversos.
  • En el procesamiento de la información , la complejidad es una medida del número total de propiedades transmitidas por un objeto y detectadas por un observador . A esta colección de propiedades a menudo se la denomina estado .
  • En los sistemas físicos , la complejidad es una medida de la probabilidad del vector de estado del sistema. Esto no debe confundirse con la entropía ; es una medida matemática distinta, una en la que dos estados distintos nunca se combinan y se consideran iguales, como se hace con la noción de entropía en la mecánica estadística .
  • En los sistemas dinámicos , la complejidad estadística mide el tamaño del programa mínimo capaz de reproducir estadísticamente los patrones (configuraciones) contenidos en el conjunto de datos (secuencia). Mientras que la complejidad algorítmica implica una descripción determinista de un objeto (mide el contenido de información de una secuencia individual), la complejidad estadística, como la complejidad del pronóstico , implica una descripción estadística y se refiere a un conjunto de secuencias generadas por una determinada fuente. Formalmente, la complejidad estadística reconstruye un modelo mínimo que comprende la colección de todas las historias que comparten un futuro probabilístico similar y mide la entropía de la distribución de probabilidad de los estados dentro de este modelo. Es una medida computable e independiente del observador basada únicamente en la dinámica interna del sistema, y ​​se ha utilizado en estudios de emergencia y autoorganización .
  • En matemáticas , la complejidad de Krohn-Rhodes es un tema importante en el estudio de semigrupos finitos y autómatas .
  • En la teoría de redes, la complejidad es el producto de la riqueza en las conexiones entre los componentes de un sistema, y ​​se define por una distribución muy desigual de ciertas medidas (algunos elementos están muy conectados y otros muy pocos, ver red compleja ).
  • En la ingeniería de software , la complejidad de la programación es una medida de las interacciones de los diversos elementos del software. Esto difiere de la complejidad computacional descrita anteriormente en que es una medida del diseño del software.
  • En resumen sentido - Resumen Complejidad, se basa en estructuras visuales percepción Es complejidad de la cadena binaria definida como un cuadrado de características número dividido por el número de elementos (0 y 1.). Las características comprenden aquí todos los arreglos distintivos de ceros y unos. Aunque el número de características siempre debe ser aproximado, la definición es precisa y cumple con un criterio intuitivo.

Otros campos introducen nociones de complejidad definidas con menos precisión:

  • Un sistema adaptativo complejo tiene algunos o todos los siguientes atributos:
    • El número de partes (y tipos de partes) en el sistema y el número de relaciones entre las partes no es trivial; sin embargo, no existe una regla general para separar "trivial" de "no trivial";
    • El sistema tiene memoria o incluye retroalimentación ;
    • El sistema puede adaptarse según su historial o retroalimentación;
    • Las relaciones entre el sistema y su entorno no son triviales ni lineales;
    • El sistema puede verse influenciado por su entorno o puede adaptarse a él;
    • El sistema es muy sensible a las condiciones iniciales.

Estudio

La complejidad siempre ha sido parte de nuestro entorno y, por lo tanto, muchos campos científicos se han ocupado de sistemas y fenómenos complejos. Desde una perspectiva, lo que de alguna manera es complejo, mostrar variación sin ser aleatorio , es más digno de interés dadas las recompensas que se encuentran en las profundidades de la exploración.

El uso del término complejo a menudo se confunde con el término complicado. En los sistemas actuales, esta es la diferencia entre una miríada de "tubos de estufa" de conexión y soluciones "integradas" eficaces. Esto significa que complejo es lo opuesto a independiente, mientras que complicado es lo opuesto a simple.

Si bien esto ha llevado a algunos campos a proponer definiciones específicas de complejidad, existe un movimiento más reciente para reagrupar observaciones de diferentes campos para estudiar la complejidad en sí misma, ya sea que aparezca en hormigueros , cerebros humanos o mercados de valores , sistemas sociales. Uno de esos grupos interdisciplinarios de campos son las teorías del orden relacional .

Temas

Comportamiento

A menudo se dice que el comportamiento de un sistema complejo se debe al surgimiento y la autoorganización . La teoría del caos ha investigado la sensibilidad de los sistemas a las variaciones en las condiciones iniciales como una de las causas del comportamiento complejo.

Mecanismos

Los desarrollos recientes en la vida artificial , la computación evolutiva y los algoritmos genéticos han llevado a un énfasis cada vez mayor en la complejidad y los sistemas adaptativos complejos .

Simulaciones

En ciencias sociales , el estudio sobre el surgimiento de macropropiedades a partir de micropropiedades, también conocido como vista macro-micro en sociología . El tema se reconoce comúnmente como una complejidad social que a menudo se relaciona con el uso de la simulación por computadora en las ciencias sociales, es decir, la sociología computacional .

Sistemas

Artículo principal: sistema complejo

La teoría de sistemas se ha preocupado durante mucho tiempo por el estudio de sistemas complejos (en tiempos recientes, la teoría de la complejidad y los sistemas complejos también se han utilizado como nombres del campo). Estos sistemas están presentes en la investigación de una variedad de disciplinas, que incluyen biología , economía , estudios sociales y tecnología . Recientemente, la complejidad se ha convertido en un dominio natural de interés de los sistemas sociocognitivos del mundo real y la investigación sistémica emergente . Los sistemas complejos tienden a ser de alta dimensión , no lineales y difíciles de modelar. En circunstancias específicas, pueden exhibir un comportamiento de baja dimensión.

Datos

En teoría de la información , la teoría algorítmica de la información se ocupa de la complejidad de las cadenas de datos.

Las cadenas complejas son más difíciles de comprimir. Si bien la intuición nos dice que esto puede depender del códec utilizado para comprimir una cadena (teóricamente, un códec podría crearse en cualquier lenguaje arbitrario, incluido uno en el que el comando muy pequeño "X" podría hacer que la computadora genere una cadena muy complicada como "18995316"), se pueden implementar dos idiomas completos de Turing entre sí, lo que significa que la longitud de dos codificaciones en diferentes idiomas variará como máximo en la longitud del idioma de "traducción", que terminará siendo insignificante durante grandes cadenas de datos.

Estas medidas algorítmicas de complejidad tienden a asignar valores altos al ruido aleatorio . Sin embargo, aquellos que estudian sistemas complejos no considerarían la aleatoriedad como complejidad.

La entropía de la información también se usa a veces en la teoría de la información como indicativo de complejidad, pero la entropía también es alta para la aleatoriedad. La complejidad de la fluctuación de la información, las fluctuaciones de la información sobre la entropía, no considera que la aleatoriedad sea compleja y ha sido útil en muchas aplicaciones.

Un trabajo reciente en aprendizaje automático ha examinado la complejidad de los datos, ya que afecta el rendimiento de los algoritmos de clasificación supervisados . Ho y Basu presentan un conjunto de medidas de complejidad para problemas de clasificación binaria .

Las medidas de complejidad cubren ampliamente:

  • las superposiciones en los valores de las características de diferentes clases.
  • la separabilidad de las clases.
  • medidas de geometría, topología y densidad de variedades . La dureza de la instancia es otro enfoque que busca caracterizar la complejidad de los datos con el objetivo de determinar qué tan difícil es clasificar correctamente un conjunto de datos y no se limita a problemas binarios.

La dureza de la instancia es un enfoque de abajo hacia arriba que primero busca identificar las instancias que probablemente estén mal clasificadas (o, en otras palabras, qué instancias son las más complejas). Las características de las instancias que es probable que se clasifiquen erróneamente se miden luego en función del resultado de un conjunto de medidas de dureza. Las medidas de dureza se basan en varias técnicas de aprendizaje supervisado, como medir el número de vecinos en desacuerdo o la probabilidad de la etiqueta de clase asignada dadas las características de entrada. La información proporcionada por las medidas de complejidad se ha examinado para su uso en el metaaprendizaje para determinar qué conjuntos de datos filtrar (o eliminar las instancias sospechosas de ruido del conjunto de entrenamiento) es más beneficioso y podría expandirse a otras áreas.

En reconocimiento molecular

Un estudio reciente basado en simulaciones moleculares y constantes de cumplimiento describe el reconocimiento molecular como un fenómeno de organización. Incluso para moléculas pequeñas como los carbohidratos , el proceso de reconocimiento no se puede predecir ni diseñar, incluso asumiendo que se conoce exactamente la fuerza de cada enlace de hidrógeno individual .

La ley de la complejidad requerida

Partiendo de la ley de la variedad requerida , Boisot y McKelvey formularon la "Ley de la complejidad requerida ", que sostiene que, para ser eficazmente adaptativo, la complejidad interna de un sistema debe coincidir con la complejidad externa que enfrenta. La aplicación en la dirección de proyectos de la Ley de la Complejidad Requisito es el análisis de la complejidad positiva, apropiada y positiva .

En la gestión de proyectos

La complejidad del proyecto es propiedad de un proyecto que hace que sea difícil comprender, prever y mantener bajo control su comportamiento general, incluso cuando se proporciona información razonablemente completa sobre el sistema del proyecto.

Aplicaciones

La teoría de la complejidad computacional es el estudio de la complejidad de los problemas, es decir, la dificultad de resolverlos . Los problemas se pueden clasificar por clase de complejidad de acuerdo con el tiempo que tarda un algoritmo, generalmente un programa de computadora, en resolverlos en función del tamaño del problema. Algunos problemas son difíciles de resolver, mientras que otros son fáciles. Por ejemplo, algunos problemas difíciles necesitan algoritmos que requieren una cantidad exponencial de tiempo en términos del tamaño del problema para resolver. Tomemos el problema del viajante de comercio , por ejemplo. Se puede resolver a tiempo (donde n es el tamaño de la red a visitar, la cantidad de ciudades que el viajante de comercio debe visitar exactamente una vez). A medida que crece el tamaño de la red de ciudades, el tiempo necesario para encontrar la ruta crece (más que) exponencialmente.

Aunque un problema puede resolverse computacionalmente en principio, en la práctica real puede que no sea tan simple. Estos problemas pueden requerir una gran cantidad de tiempo o una cantidad excesiva de espacio. La complejidad computacional puede abordarse desde muchos aspectos diferentes. La complejidad computacional se puede investigar sobre la base del tiempo, la memoria u otros recursos utilizados para resolver el problema. El tiempo y el espacio son dos de las consideraciones más importantes y populares cuando se analizan problemas de complejidad.

Existe una cierta clase de problemas que, si bien son solucionables en principio, requieren tanto tiempo o espacio que no es práctico intentar resolverlos. Estos problemas se denominan intratables .

Existe otra forma de complejidad llamada complejidad jerárquica . Es ortogonal a las formas de complejidad discutidas hasta ahora, que se denominan complejidad horizontal.

Ver también

Referencias

Otras lecturas

enlaces externos