Existe uma relação entre a teoria da complexidade computacional e a teoria dos sistemas complexos?

A teoria da complexidade computacional classifica os problemas de acordo com a dificuldade inerente.

A teoria de sistemas complexos trata de sistemas que exibem comportamentos que obviamente não surgem das propriedades das partes individuais do sistema. Exemplos incluem sistemas caóticos, sistemas adaptativos complexos ou sistemas não lineares.

Existe alguma ponte formal entre esses campos?

Pelo que vale, a noção de realizar criptografia com autômatos celulares não é nova e, no início deste ano , Applebaum, Ishai e Kushilevitz identificaram "complexidade" com intratabilidade computacional.

Este artigo de Kanter, Kopelowitz e Kinzel, Public Channel Cryptography: Chaos Synchronization e o Décimo Problema de Hilbert mostra que existe uma forte conexão entre dinâmica não linear e problemas NP-completos com a promessa de novos protocolos de canal público seguros.

Phys. Rev. Lett. 101, 084102 (2008)