Complexidade - Complexity

A complexidade caracteriza o comportamento de um sistema ou modelo cujos componentes interagem de várias maneiras e seguem regras locais, o que significa que não existe uma instrução superior razoável para definir as várias interações possíveis.

O termo é geralmente usado para caracterizar algo com muitas partes, onde essas partes interagem entre si de várias maneiras, culminando em uma ordem superior de emergência maior do que a soma de suas partes. O estudo dessas ligações complexas em várias escalas é o objetivo principal da teoria dos sistemas complexos .

A partir de 2010, a ciência adota uma série de abordagens para caracterizar a complexidade; Zayed et al. refletem muitos deles. Neil Johnson afirma que "mesmo entre os cientistas, não há uma definição única de complexidade - e a noção científica tem sido tradicionalmente transmitida usando exemplos particulares ..." Em última análise, Johnson adota a definição de "ciência da complexidade" como "o estudo dos fenômenos que emergir de uma coleção de objetos em interação ".

Visão geral

As definições de complexidade muitas vezes dependem do conceito de " sistema " - um conjunto de partes ou elementos que têm relações entre si diferenciadas de relações com outros elementos fora do regime relacional. Muitas definições tendem a postular ou presumir que a complexidade expressa uma condição de numerosos elementos em um sistema e numerosas formas de relacionamento entre os elementos. No entanto, o que se vê como complexo e o que se vê como simples é relativo e muda com o tempo.

Warren Weaver postulou em 1948 duas formas de complexidade: complexidade desorganizada e complexidade organizada. Fenômenos de 'complexidade desorganizada' são tratados usando a teoria da probabilidade e mecânica estatística, enquanto 'complexidade organizada' lida com fenômenos que escapam de tais abordagens e se confrontam "lidando simultaneamente com um número considerável de fatores que estão inter-relacionados em um todo orgânico". O artigo de Weaver de 1948 influenciou o pensamento subsequente sobre a complexidade.

As abordagens que incorporam conceitos de sistemas, múltiplos elementos, múltiplos regimes relacionais e espaços de estado podem ser resumidas como implicando que a complexidade surge do número de regimes relacionais distinguíveis (e seus espaços de estado associados) em um sistema definido.

Algumas definições referem-se à base algorítmica para a expressão de um fenômeno complexo ou modelo ou expressão matemática, conforme estabelecido posteriormente neste documento.

Desorganizado x organizado

Um dos problemas em abordar questões de complexidade tem sido formalizar a distinção conceitual intuitiva entre o grande número de variações nos relacionamentos existentes em coleções aleatórias, e o às vezes grande, mas menor, número de relacionamentos entre os elementos em sistemas onde as restrições (relacionadas à correlação de de outra forma, elementos independentes) reduzem simultaneamente as variações da independência do elemento e criam regimes distinguíveis de relacionamentos ou interações mais uniformes ou correlacionados.

Weaver percebeu e abordou este problema, pelo menos de uma forma preliminar, ao traçar uma distinção entre "complexidade desorganizada" e "complexidade organizada".

Na visão de Weaver, a complexidade desorganizada resulta do sistema particular ter um grande número de partes, digamos milhões de partes, ou muito mais. Embora as interações das partes em uma situação de "complexidade desorganizada" possam ser vistas como amplamente aleatórias, as propriedades do sistema como um todo podem ser compreendidas pelo uso de métodos estatísticos e de probabilidade.

Um excelente exemplo de complexidade desorganizada é um gás em um recipiente, com as moléculas de gás como as partes. Alguns sugeririam que um sistema de complexidade desorganizada pode ser comparado com a simplicidade (relativa) das órbitas planetárias - a última pode ser prevista aplicando-se as leis do movimento de Newton . Claro, a maioria dos sistemas do mundo real, incluindo órbitas planetárias, eventualmente se tornam teoricamente imprevisíveis, mesmo usando a dinâmica newtoniana; conforme descoberto pela moderna teoria do caos .

A complexidade organizada, na visão de Weaver, reside em nada mais do que a interação não aleatória, ou correlacionada, entre as partes. Esses relacionamentos correlacionados criam uma estrutura diferenciada que pode, como um sistema, interagir com outros sistemas. O sistema coordenado manifesta propriedades não realizadas ou ditadas por partes individuais. Pode-se dizer que o aspecto organizado dessa forma de complexidade vis-à-vis a outros sistemas que não o sistema sujeito "surge", sem qualquer "mão orientadora".

O número de peças não precisa ser muito grande para que um determinado sistema tenha propriedades emergentes. Um sistema de complexidade organizada pode ser compreendido em suas propriedades (comportamento entre as propriedades) por meio de modelagem e simulação , principalmente modelagem e simulação com computadores . Um exemplo de complexidade organizada é um bairro da cidade como mecanismo vivo, com as pessoas da vizinhança entre as partes do sistema.

Fontes e fatores

Geralmente, existem regras que podem ser invocadas para explicar a origem da complexidade em um determinado sistema.

A fonte da complexidade desorganizada é o grande número de partes no sistema de interesse e a falta de correlação entre os elementos do sistema.

No caso de sistemas vivos auto-organizados, a complexidade proveitosamente organizada vem de organismos mutantes benéficos selecionados para sobreviver por seu ambiente por sua capacidade reprodutiva diferencial ou pelo menos sucesso sobre matéria inanimada ou organismos complexos menos organizados. Veja, por exemplo , o tratamento de ecossistemas de Robert Ulanowicz .

A complexidade de um objeto ou sistema é uma propriedade relativa. Por exemplo, para muitas funções (problemas), uma complexidade computacional como o tempo de computação é menor quando máquinas de Turing com várias fitas são usadas do que quando máquinas de Turing com uma fita são usadas. As máquinas de acesso aleatório permitem diminuir ainda mais a complexidade do tempo (Greenlaw e Hoover 1998: 226), enquanto as máquinas de Turing indutivas podem diminuir até mesmo a classe de complexidade de uma função, linguagem ou conjunto (Burgin 2005). Isso mostra que as ferramentas de atividade podem ser um fator importante de complexidade.

Significados variados

Em vários campos científicos, "complexidade" tem um significado preciso:

• Na teoria da complexidade computacional , são estudados os montantes de recursos necessários para a execução de algoritmos . Os tipos mais populares de complexidade computacional são a complexidade de tempo de um problema igual ao número de etapas que leva para resolver uma instância do problema em função do tamanho da entrada (geralmente medido em bits), usando o mais eficiente algoritmo, e a complexidade espacial de um problema igual ao volume da memória usada pelo algoritmo (por exemplo, células da fita) que leva para resolver uma instância do problema em função do tamanho da entrada (geralmente medido em bits), usando o algoritmo mais eficiente. Isso permite a classificação de problemas computacionais por classe de complexidade (como P , NP , etc.). Uma abordagem axiomática para a complexidade computacional foi desenvolvida por Manuel Blum . Ele permite deduzir muitas propriedades de medidas concretas de complexidade computacional, como complexidade de tempo ou complexidade de espaço, a partir de propriedades de medidas definidas axiomaticamente.
• Na teoria da informação algorítmica , a complexidade de Kolmogorov (também chamada de complexidade descritiva , complexidade algorítmica ou entropia algorítmica ) de uma string é o comprimento do programa binário mais curto que produz aquela string. O comprimento mínimo da mensagem é uma aplicação prática desta abordagem. Diferentes tipos de complexidade de Kolmogorov são estudados: complexidade uniforme, complexidade de prefixo, complexidade monótona, complexidade de Kolmogorov limitada pelo tempo e complexidade de Kolmogorov limitada pelo espaço. Uma abordagem axiomática da complexidade de Kolmogorov baseada nos axiomas de Blum (Blum 1967) foi introduzida por Mark Burgin no artigo apresentado para publicação por Andrey Kolmogorov . A abordagem axiomática abrange outras abordagens da complexidade de Kolmogorov. É possível tratar diferentes tipos de complexidade de Kolmogorov como casos particulares de complexidade de Kolmogorov generalizada definida axiomaticamente. Em vez de provar teoremas semelhantes, como o teorema da invariância básica, para cada medida particular, é possível deduzir facilmente todos esses resultados de um teorema correspondente provado no cenário axiomático. Esta é uma vantagem geral da abordagem axiomática em matemática. A abordagem axiomática da complexidade de Kolmogorov foi desenvolvida no livro (Burgin 2005) e aplicada a métricas de software (Burgin e Debnath, 2003; Debnath e Burgin, 2003).
• Na teoria da informação , a complexidade da flutuação da informação é a flutuação da informação sobre a entropia da informação . É derivado de flutuações na predominância da ordem e do caos em um sistema dinâmico e tem sido usado como uma medida de complexidade em muitos campos diversos.
• No processamento de informações , a complexidade é uma medida do número total de propriedades transmitidas por um objeto e detectadas por um observador . Essa coleção de propriedades costuma ser chamada de estado .
• Em sistemas físicos , a complexidade é uma medida da probabilidade do vetor de estado do sistema. Isso não deve ser confundido com entropia ; é uma medida matemática distinta, na qual dois estados distintos nunca são combinados e considerados iguais, como é feito para a noção de entropia na mecânica estatística .
• Em sistemas dinâmicos , a complexidade estatística mede o tamanho do programa mínimo capaz de reproduzir estatisticamente os padrões (configurações) contidos no conjunto de dados (sequência). Enquanto a complexidade algorítmica implica uma descrição determinística de um objeto (ela mede o conteúdo de informação de uma sequência individual), a complexidade estatística, como a complexidade de previsão , implica uma descrição estatística e se refere a um conjunto de sequências geradas por uma determinada fonte. Formalmente, a complexidade estatística reconstrói um modelo mínimo compreendendo a coleção de todas as histórias que compartilham um futuro probabilístico semelhante e mede a entropia da distribuição de probabilidade dos estados dentro desse modelo. É uma medida computável e independente do observador, baseada apenas na dinâmica interna do sistema, e tem sido usada em estudos de emergência e auto-organização .
• Em matemática , a complexidade de Krohn-Rhodes é um tópico importante no estudo de semigrupos finitos e autômatos .
• Na teoria da rede, a complexidade é o produto da riqueza das conexões entre os componentes de um sistema, e definida por uma distribuição muito desigual de certas medidas (alguns elementos sendo altamente conectados e alguns muito poucos, ver rede complexa ).
• Na engenharia de software , a complexidade da programação é uma medida das interações dos vários elementos do software. Isso difere da complexidade computacional descrita acima porque é uma medida do design do software.
• Em sentido abstrato - Complexidade Abstrata, é baseada na percepção de estruturas visuais. É a complexidade da string binária definida como um quadrado do número de características dividido pelo número de elementos (0's e 1's). Os recursos compreendem aqui todos os arranjos distintos de 0's e 1's. Embora o número de recursos deva ser sempre aproximado, a definição é precisa e atende a critérios intuitivos.

Outros campos introduzem noções de complexidade definidas com menos precisão:

• Um sistema adaptativo complexo tem alguns ou todos os seguintes atributos:
  • O número de partes (e tipos de partes) no sistema e o número de relações entre as partes não é trivial - entretanto, não existe uma regra geral para separar "trivial" de "não trivial";
  • O sistema possui memória ou inclui feedback ;
  • O sistema pode se adaptar de acordo com sua história ou feedback;
  • As relações entre o sistema e seu ambiente são não triviais ou não lineares;
  • O sistema pode ser influenciado por, ou pode se adaptar a, seu ambiente;
  • O sistema é altamente sensível às condições iniciais.

Estude

A complexidade sempre fez parte do nosso ambiente e, portanto, muitos campos científicos lidaram com sistemas e fenômenos complexos. De uma perspectiva, o que é de alguma forma complexo - exibir variação sem ser aleatório - é mais digno de interesse, dadas as recompensas encontradas nas profundezas da exploração.

O uso do termo complexo é freqüentemente confundido com o termo complicado. Nos sistemas atuais, esta é a diferença entre uma miríade de "chaminés" de conexão e soluções "integradas" eficazes. Isso significa que complexo é o oposto de independente, enquanto complicado é o oposto de simples.

Embora isso tenha levado alguns campos a apresentarem definições específicas de complexidade, há um movimento mais recente para reagrupar observações de diferentes campos para estudar a complexidade em si mesma, quer ela apareça em formigueiros , cérebros humanos ou mercados de ações , sistemas sociais. Um desses grupos de campos interdisciplinares são as teorias de ordem relacional .

Tópicos

Comportamento

Costuma-se dizer que o comportamento de um sistema complexo é devido ao surgimento e à auto-organização . A teoria do caos investigou a sensibilidade dos sistemas às variações nas condições iniciais como uma das causas do comportamento complexo.

Mecanismos

Desenvolvimentos recentes em vida artificial , computação evolutiva e algoritmos genéticos levaram a uma ênfase crescente na complexidade e em sistemas adaptativos complexos .

Simulações

Nas ciências sociais , o estudo sobre a emergência de macro-propriedades a partir das micro-propriedades, também conhecidas como macro-micro-visão na sociologia . O tema é comumente reconhecido como complexidade social, muitas vezes relacionado ao uso de simulação computacional nas ciências sociais, ou seja: sociologia computacional .

Sistemas

A teoria dos sistemas há muito se preocupa com o estudo de sistemas complexos (nos últimos tempos, a teoria da complexidade e os sistemas complexos também têm sido usados ​​como nomes do campo). Esses sistemas estão presentes na pesquisa de uma variedade de disciplinas, incluindo biologia , economia , estudos sociais e tecnologia . Recentemente, a complexidade tornou-se um domínio natural de interesse dos sistemas sócio-cognitivos do mundo real e da pesquisa sistêmica emergente . Sistemas complexos tendem a ser altamente dimensionais , não lineares e difíceis de modelar. Em circunstâncias específicas, eles podem exibir comportamento de baixa dimensão.

Dados

Na teoria da informação , a teoria algorítmica da informação se preocupa com a complexidade das cadeias de dados.

Cordas complexas são mais difíceis de compactar. Embora a intuição nos diga que isso pode depender do codec usado para compactar uma string (um codec pode ser teoricamente criado em qualquer linguagem arbitrária, incluindo uma em que o comando muito pequeno "X" pode fazer com que o computador produza uma string muito complicada como "18995316"), quaisquer duas linguagens de Turing-complete podem ser implementadas uma na outra, o que significa que o comprimento de duas codificações em diferentes idiomas irá variar no máximo em relação ao comprimento da linguagem de "tradução" - que acabará sendo insignificante por suficiente grandes cadeias de dados.

Essas medidas algorítmicas de complexidade tendem a atribuir altos valores ao ruído aleatório . No entanto, aqueles que estudam sistemas complexos não consideram a aleatoriedade como complexidade.

A entropia da informação às vezes também é usada na teoria da informação como indicativo de complexidade, mas a entropia também é alta para a aleatoriedade. A complexidade da flutuação da informação, flutuações da informação sobre entropia, não considera a aleatoriedade como complexa e tem sido útil em muitas aplicações.

Trabalhos recentes em aprendizado de máquina examinaram a complexidade dos dados, pois afetam o desempenho de algoritmos de classificação supervisionados . Ho e Basu apresentam um conjunto de medidas de complexidade para problemas de classificação binária .

As medidas de complexidade abrangem amplamente:

• as sobreposições em valores de recursos de classes diferentes.
• a separabilidade das classes.
• medidas de geometria, topologia e densidade de variedades . A dureza da instância é outra abordagem que busca caracterizar a complexidade dos dados com o objetivo de determinar o quão difícil um conjunto de dados é para classificar corretamente e não se limita a problemas binários.

A dureza da instância é uma abordagem de baixo para cima que busca primeiro identificar as instâncias que provavelmente serão classificadas incorretamente (ou, em outras palavras, quais são as instâncias mais complexas). As características das instâncias que provavelmente serão classificadas incorretamente são então medidas com base na saída de um conjunto de medidas de dureza. As medidas de dureza são baseadas em várias técnicas de aprendizado supervisionado, como medir o número de vizinhos discordantes ou a probabilidade do rótulo de classe atribuído, dados os recursos de entrada. As informações fornecidas pelas medidas de complexidade foram examinadas para uso em meta-aprendizado para determinar para quais filtros de conjuntos de dados (ou remover instâncias suspeitas de ruído do conjunto de treinamento) é a mais benéfica e pode ser expandida para outras áreas.

Em reconhecimento molecular

Um estudo recente baseado em simulações moleculares e constantes de conformidade descreve o reconhecimento molecular como um fenômeno de organização. Mesmo para moléculas pequenas como carboidratos , o processo de reconhecimento não pode ser previsto ou projetado, mesmo supondo que a força de cada ligação de hidrogênio individual seja exatamente conhecida.

A lei da complexidade necessária

Partindo da lei da variedade de requisitos , Boisot e McKelvey formularam a 'Lei da Complexidade de Requisito', que afirma que, para ser eficazmente adaptativo, a complexidade interna de um sistema deve corresponder à complexidade externa que ele enfrenta. A aplicação na gestão de projetos da Lei da Complexidade de Requisitos é a análise da complexidade positiva, adequada e positiva .

Em gerenciamento de projetos

A complexidade do projeto é propriedade de um projeto que torna difícil entender, prever e manter sob controle seu comportamento geral, mesmo quando recebe informações razoavelmente completas sobre o sistema do projeto.

Formulários

A teoria da complexidade computacional é o estudo da complexidade dos problemas - ou seja, a dificuldade de resolvê- los. Os problemas podem ser classificados por classe de complexidade de acordo com o tempo que leva para um algoritmo - geralmente um programa de computador - resolvê-los em função do tamanho do problema. Alguns problemas são difíceis de resolver, enquanto outros são fáceis. Por exemplo, alguns problemas difíceis precisam de algoritmos que levam uma quantidade de tempo exponencial em termos do tamanho do problema para serem resolvidos. Veja o problema do caixeiro viajante , por exemplo. Pode ser resolvido com o tempo (onde n é o tamanho da rede a ser visitada - o número de cidades que o caixeiro viajante deve visitar exatamente uma vez). Conforme o tamanho da rede de cidades aumenta, o tempo necessário para encontrar a rota aumenta (mais do que) exponencialmente. ${\ displaystyle O (n ^ {2} 2 ^ {n})}$

Mesmo que um problema possa ser resolvido computacionalmente em princípio, na prática real pode não ser tão simples. Esses problemas podem exigir muito tempo ou uma quantidade excessiva de espaço. A complexidade computacional pode ser abordada de muitos aspectos diferentes. A complexidade computacional pode ser investigada com base no tempo, memória ou outros recursos usados ​​para resolver o problema. Tempo e espaço são duas das considerações mais importantes e populares quando problemas de complexidade são analisados.

Existe uma certa classe de problemas que, embora sejam solucionáveis ​​em princípio, requerem tanto tempo ou espaço que não é prático tentar resolvê-los. Esses problemas são chamados de intratáveis .

Existe outra forma de complexidade chamada complexidade hierárquica . É ortogonal às formas de complexidade discutidas até agora, que são chamadas de complexidade horizontal.

Veja também

Referências

Leitura adicional

links externos

• Medidas de complexidade - um artigo sobre a abundância de medidas de complexidade não tão úteis.
• Explorando a Complexidade em Ciência e Tecnologia Arquivado em 05/03/2011 na Wayback Machine - Curso introdutório a sistemas complexos por Melanie Mitchell
• Instituto Santa Fe com foco no estudo da ciência da complexidade: vídeos de palestras
• UC Four Campus Complexity Videoconferences - Human Sciences and Complexity