9
$\begingroup$

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 is not new, and earlier this year Applebaum, Ishai, and Kushilevitz identified "complexity" with computational intractability.

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
4
$\begingroup$

This paper by Kanter, Kopelowitz, and Kinzel, Public Channel Cryptography: Chaos Synchronization and Hilbert’s Tenth Problem 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)

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, @turkistany. I also found some interesting references to the notion of AI-completeness...! $\endgroup$
    – rphv
    Commented Nov 18, 2010 at 2:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.