Czy istnieje związek między teorią złożoności obliczeniowej a teorią systemów złożonych?

Teoria złożoności obliczeniowej klasyfikuje problemy według ich nieodłącznej trudności.

Teoria złożonych systemów dotyczy systemów, które wykazują zachowania, które oczywiście nie wynikają z właściwości poszczególnych części systemu. Przykłady obejmują systemy chaotyczne, złożone systemy adaptacyjne lub systemy nieliniowe.

Czy istnieje formalny pomost między tymi polami?

Co do tego, co jest warte, koncepcja wykonywania kryptografii za pomocą automatów komórkowych nie jest nowa, a wcześniej w tym roku Applebaum, Ishai i Kushilevitz zidentyfikowali „złożoność” z trudnością obliczeniową.

Ten artykuł Kantera, Kopelowitza i Kinzela, Public Channel Cryptography: Chaos Synchronization i Hilbert's Tent Problem pokazuje, że istnieje silny związek między dynamiką nieliniową i problemami NP-zupełnymi z obietnicą nowych bezpiecznych protokołów kanału publicznego.

Phys. Wielebny Lett. 101, 084102 (2008)