¿Existe una relación entre la teoría de la complejidad computacional y la teoría de sistemas complejos?

9

La teoría de la complejidad computacional clasifica los problemas de acuerdo con su dificultad inherente.

La teoría de sistemas complejos aborda sistemas que exhiben comportamientos que obviamente no surgen de las propiedades de las partes individuales del sistema. Los ejemplos incluyen sistemas caóticos, sistemas adaptativos complejos o sistemas no lineales.

¿Hay algún puente formal entre estos campos?

Por lo que vale, la noción de realizar criptografía con autómatas celulares no es nueva, y a principios de este año Applebaum, Ishai y Kushilevitz identificaron la "complejidad" con la intratabilidad computacional.

cc.complexity-theory soft-question big-picture rphv
fuente
Dick Lipton
Artem Kaznatcheev hace
ver también relación entre cs y sistemas dinámicos complejos . el estudio del tiempo de Lorentz / diferencial de la ecuación como se menciona en Liptons blog es también un lugar bueno para empezar
VZN

Respuestas:

4

Este documento de Kanter, Kopelowitz y Kinzel, Public Channel Cryptography: Chaos Synchronization y Hilbert's Décimo problema muestra que existe una fuerte conexión entre la dinámica no lineal y los problemas NP-completos con la promesa de nuevos protocolos seguros de canal público.

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

Mohammad Al-Turkistany
fuente
Gracias, @turkistany. ¡También encontré algunas referencias interesantes a la noción de integridad de AI ...!
rphv