Ing. De Sistemas

Definición de complejidad

Complejidad es la cualidad de lo que está compuesto de diversos elementos. En términos generales, la complejidad tiende a ser utilizada para caracterizar algo con muchas partes que forman un conjunto intrincado.
Desde un punto de vista etimológico, la palabra complejidad es de origen latino, proviene de complectere, cuya raíz plectere significa trenzar, enlazar. Elagregado del prefijo “com” añade el sentido de la dualidad de dos elementos opuestos que se enlazan íntimamente, pero sin anular su dualidad. De allí que “complectere” se utilice tanto para referirse al combate entre dos guerreros, como al entrelazamiento de dos amantes. La complejidad y sus implicaciones son las bases del denominado pensamiento complejo de Edgar Morin.

Sistema complejo
UnSistema Complejo está compuesto por varias partes interconectadas o entrelazadas cuyos vínculos crean información adicional no visible antes por el observador. Como resultado de las interacciones entre elementos, surgen propiedades nuevas que no pueden explicarse a partir de las propiedades de los elementos aislados. Dichas propiedades se denominan propiedades emergentes.
El sistema complicado, encontraposición, también está formado por varias partes pero los enlaces entre éstas no añaden información adicional. Nos basta con saber cómo funciona cada una de ellas para entender el sistema. En un sistema complejo, en cambio, existen variables ocultas cuyo desconocimiento nos impide analizar el sistema con precisión. Así pues, un sistema complejo, posee más información que la que da cada parteindependientemente. Para describir un sistema complejo hace falta no solo conocer el funcionamiento de las partes sino conocer como se relacionan entre sí.
Ejemplos:
Un ejemplo típico de sistema complejo es la Tierra.
La tierra está formada por varios sistemas simples que la describen:
• Campo gravitatorio.
• Campo magnético.
• Flujo térmico.
• Ondas elásticas.
•Geodinámica.
• Humanidad.

Cada uno de estos sistemas está bien estudiado pero desconocemos la forma en que interactúan y hacen evolucionar el sistema 'Tierra'. Hay, pues, mucha más información oculta en esas interrelaciones de sistemas.

Otros sistemas complejos típicos son:
• El tiempo atmosférico.
• Terremotos y volcanes.
• Los ecosistemas.
• Los seres vivos.
• Laconciencia.
• Las Sociedades.
• Las Ciudades.

La teoría de la complejidad computacional es la rama de la teoría de la computación que estudia, de manera teórica, la complejidad inherente a la resolución de un problema computable. Los recursos comúnmente estudiados son el tiempo (mediante una aproximación al número y tipo de pasos de ejecución de un algoritmo para resolver un problema) yel espacio (mediante una aproximación a la cantidad de memoria utilizada para resolver un problema). Se pueden estudiar igualmente otros parámetros, tales como el número de procesadores necesarios para resolver el problema en paralelo. La teoría de la complejidad difiere de la teoría de la computabilidad en que ésta se ocupa de la factibilidad de expresar problemas como algoritmos efectivos sintomar en cuenta los recursos necesarios para ello.

Los problemas que tienen una solución con orden de complejidad lineal son los problemas que se resuelven en un tiempo que se relaciona linealmente con su tamaño.

Hoy en día las computadoras resuelven problemas mediante algoritmos que tienen como máximo una complejidad o coste computacional polinómico, es decir, la relación entre el tamaño delproblema y su tiempo de ejecución es polinómica. Éstos son problemas agrupados en la clase P. Los problemas que no pueden ser resueltos por nuestras computadoras (las cuales son Máquinas Determinísticas), que en general poseen costes factorial o combinatorio pero que podrían ser procesados por una máquina no-determinista, están agrupados en la clase NP. Estos problemas no tienen una solución...