<p>This paper by Kanter, Kopelowitz, and  Kinzel, <a href="http://prl.aps.org/abstract/PRL/v101/i8/e084102" rel="nofollow">Public Channel Cryptography: Chaos Synchronization and Hilbert’s Tenth Problem</a> shows that there is a strong connection between nonlinear dynamics and NP-complete problems with the promise of novel secure public-channel protocols.</p>

<p>Phys. Rev. Lett. 101, 084102 (2008)</p>

CC BY-SA 2.5
2010-11-18T02:46:00.780Z
Thanks, @turkistany.  I also found some interesting references to the notion of _AI-completeness_...!
rphv
CC BY-SA 2.5
2010-11-17T22:52:06.640Z
2010-11-17T23:30:44.173Z
2010-11-17T23:30:44.173Z
Mohammad Al-Turkistany
<p><strong>Computational complexity theory</strong> classifies problems according to their inherent difficulty.</p>

<p><strong>Complex systems theory</strong> addresses systems that exhibit behaviours that do not obviously arise from the properties of the system's individual parts.  Examples include chaotic systems, complex adaptive systems, or nonlinear systems.</p>

<p>Is there any formal bridge between these fields?</p>

<p>For what it's worth, the notion of performing <a href="http://www.stephenwolfram.com/publications/articles/ca/85-cryptography/1/text.html">cryptography with cellular automata</a> is not new, and earlier this year
<a href="http://www.eng.tau.ac.il/~bennyap/pubs/CA.pdf">Applebaum, Ishai, and Kushilevitz</a> identified "complexity" with computational intractability.</p>

CC BY-SA 3.0
2011-05-17T06:56:57.813Z
a [similar question](http://rjlipton.wordpress.com/2011/02/21/butterflies-and-complexity-theories/) is asked by Dick Lipton
Artem Kaznatcheev
CC BY-SA 3.0
2012-09-08T17:23:29.677Z
see also [relationship between cs and complex dynamical systems](http://cs.stackexchange.com/questions/2637/historical-relation-between-computer-science-and-the-theory-of-dynamical-systems/3443). the study of the lorentz weather/differential eqn as mentioned in liptons blog is also a good place to start
vzn
<cc.complexity-theory><soft-question><big-picture>
Is there a relationship between computational complexity theory and complex systems theory?
rphv
# Is there a relationship between computational complexity theory and complex systems theory?

(Asked by: username_0 on 2010-11-17)

**Computational complexity theory** classifies problems according to their inherent difficulty.

**Complex systems theory** addresses systems that exhibit behaviours that do not obviously arise from the properties of the system's individual parts. Examples include chaotic systems, complex adaptive systems, or nonlinear systems.

Is there any formal bridge between these fields?

For what it's worth, the notion of performing [cryptography with cellular automata](http://www.stephenwolfram.com/publications/articles/ca/85-cryptography/1/text.html) is not new, and earlier this year
[Applebaum, Ishai, and Kushilevitz](http://www.eng.tau.ac.il/~bennyap/pubs/CA.pdf) identified "complexity" with computational intractability.

**Tags:** cc.complexity-theory, soft-question, big-picture
> **Comments:**
> **username_1**: a [similar question](http://rjlipton.wordpress.com/2011/02/21/butterflies-and-complexity-theories/) is asked by Dick Lipton  
> **username_2**: see also [relationship between cs and complex dynamical systems](http://cs.stackexchange.com/questions/2637/historical-relation-between-computer-science-and-the-theory-of-dynamical-systems/3443). the study of the lorentz weather/differential eqn as mentioned in liptons blog is also a good place to start  

---

## 1 answers

### Answer by username_3 on 2010-11-17. Score: 4 | Accepted answer

This paper by Kanter, Kopelowitz, and Kinzel, [Public Channel Cryptography: Chaos Synchronization and Hilbert’s Tenth Problem](http://prl.aps.org/abstract/PRL/v101/i8/e084102) shows that there is a strong connection between nonlinear dynamics and NP-complete problems with the promise of novel secure public-channel protocols.

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

> **Comments:**
> **username_0**: Thanks, @turkistany.  I also found some interesting references to the notion of _AI-completeness_...!  

---

