Существует ли связь между теорией вычислительной сложности и теорией сложных систем?

Теория сложности вычислений классифицирует проблемы в соответствии с их сложностью.

Теория сложных систем обращается к системам, которые демонстрируют поведение, которое, очевидно, не вытекает из свойств отдельных частей системы. Примеры включают хаотические системы, сложные адаптивные системы или нелинейные системы.

Есть ли формальный мост между этими полями?

Что бы это ни стоило, идея выполнения криптографии с клеточными автоматами не нова, и в начале этого года Эпплбаум, Ишай и Кушилевиц определили «сложность» с вычислительной неразрешимостью.

Эта статья Kanter, Kopelowitz и Kinzel, « Криптография в публичном канале: синхронизация хаоса и десятая проблема Гильберта» показывает, что существует тесная связь между нелинейной динамикой и задачами, полными NP, с обещанием новых безопасных протоколов публичных каналов.

Phys. Преподобный Летт. 101, 084102 (2008)