La théorie de la complexité informatique classe les problèmes en fonction de leur difficulté inhérente.
La théorie des systèmes complexes aborde les systèmes qui présentent des comportements qui ne découlent évidemment pas des propriétés des différentes parties du système. Les exemples incluent les systèmes chaotiques, les systèmes adaptatifs complexes ou les systèmes non linéaires.
Existe-t-il un pont formel entre ces domaines?
Pour ce qu'elle vaut, la notion de cryptographie avec des automates cellulaires n'est pas nouvelle, et au début de cette année, Applebaum, Ishai et Kushilevitz ont identifié la «complexité» avec l' intractabilité informatique.
Réponses:
Cet article de Kanter, Kopelowitz et Kinzel, Public Channel Cryptography: Chaos Synchronization et Hilbert's Tenth Problem montre qu'il existe un lien étroit entre la dynamique non linéaire et les problèmes NP-complets avec la promesse de nouveaux protocoles sécurisés de canal public.
Phys. Rev. Lett. 101, 084102 (2008)
la source