Apakah ada hubungan antara teori kompleksitas komputasi dan teori sistem kompleks?

9

Teori kompleksitas komputasi mengklasifikasikan masalah berdasarkan kesulitannya.

Teori sistem kompleks membahas sistem yang menunjukkan perilaku yang tidak jelas muncul dari sifat-sifat bagian individu sistem. Contohnya termasuk sistem kacau, sistem adaptif yang kompleks, atau sistem nonlinier.

Apakah ada jembatan formal antara bidang-bidang ini?

Untuk apa nilainya, gagasan melakukan kriptografi dengan automata seluler bukanlah hal baru, dan awal tahun ini Applebaum, Ishai, dan Kushilevitz mengidentifikasi "kerumitan" dengan ketangguhan komputasi.

cc.complexity-theory soft-question big-picture rphv
sumber
sebuah pertanyaan serupa diminta oleh Dick Lipton
Artem Kaznatcheev
lihat juga hubungan antara cs dan sistem dinamis yang kompleks . studi tentang lorentz cuaca / diferensial eqn sebagaimana disebutkan dalam blog liptons juga merupakan tempat yang baik untuk memulai
vzn

Jawaban:

4

Makalah ini oleh Kanter, Kopelowitz, dan Kinzel, Public Channel Cryptography: Chaos Synchronization dan Hilbert's Tenth Problem menunjukkan bahwa ada hubungan yang kuat antara dinamika nonlinear dan masalah lengkap NP dengan janji protokol saluran publik yang aman.

Phys Pdt. Lett. 101, 084102 (2008)

Mohammad Al-Turkistany
sumber
Terima kasih, @turkistany. Saya juga menemukan beberapa referensi menarik tentang pengertian AI-kelengkapan ...!
rphv