Aplikasi Teori Kompleksitas

18

Teori kompleksitas tampaknya menangkap sesuatu yang mendasar tentang struktur alam semesta, dalam arti ia memformalkan gagasan intuitif bahwa beberapa masalah lebih sulit daripada yang lain.

Scott Aaronson meramalkan , "Asumsi Kekerasan NP pada akhirnya akan dilihat sebagai analog dengan Hukum Kedua Termodinamika atau ketidakmungkinan pensinyalan superluminal."

Apa yang disebut "masalah sulit" adalah dasar dari kriptografi modern.

Apakah ada aplikasi lain yang memanfaatkan, bergantung pada, atau mencontohkan adanya masalah sulit komputasi?

cc.complexity-theory soft-question big-picture rphv
sumber

Jawaban:

14

Masalah terbaru CACM memiliki artikel oleh Faliszewski, Hemaspaandra dan Hemaspaandra tentang penggunaan teori kompleksitas dalam bidang teori pilihan sosial dan desain pemilihan pada khususnya. Salah satu contoh dari hasil seperti itu adalah bahwa sementara teorema Arrow menjamin bahwa setiap sistem pemilu 'dapat diretas', mungkin NP-sulit untuk melakukannya.

Suresh Venkat
sumber
1
Saya tidak membaca makalah itu, tetapi tampaknya penulis sedang merancang sistem e-voting yang aman. Bukankah itu aplikasi kriptografi ke sistem keamanan? Perhatikan bahwa OP meminta aplikasi dari masalah sulit untuk bidang lain selain kriptografi.
MS Dousti
2
Tidak, itu tidak benar. Mereka melihat matematika sistem pemungutan suara dan mencoba memahami bagaimana perspektif teori kompleksitas mengubah pilihan desain. Misalnya, di antara tiga skema yang terlihat serupa, satu adalah NP-sulit untuk diretas dan yang lainnya tidak. Ini adalah pandangan komputasi pada teori pilihan sosial, seperti halnya crypto modern memberikan perspektif komputasi pada penyandian rahasia.
Suresh Venkat
7

ϵϵ1/ϵ

Daniel Apon
sumber
Selain itu: Kriptografi jelas merupakan aplikasi positif dari masalah yang sulit secara komputasi. Ini akan menjadi contoh penerapan teorema kompleksitas di luar bidang kompleksitas yang negatif . Apakah Anda tertarik pada satu di atas yang lain, @rphv?
Daniel Apon
1
Saya tertarik pada aplikasi positif dan negatif. Jika keberadaan masalah yang sulit secara komputasional adalah analog dengan 2LOT atau C, maka saya merasa kita harus menabrak contoh / konsekuensi dari itu sering, seperti kita sering menemukan objek dunia nyata yang 'mewujudkan' sifat-sifat tersebut (mesin mobil, listrik, dll.) Bahkan jika kita tidak "mendapatkan apa-apa" (seperti kripto) dari kenyataan bahwa ada masalah sulit, saya pikir mungkin berguna untuk mempertimbangkan keberadaan masalah sulit ketika berpikir tentang dunia. Dengan kata lain, "Bagaimana keberadaan masalah yang sulit mempengaruhi kehidupan kita?"
rphv
3

BPPP=BPP

Mohammad Al-Turkistany
sumber
2

Dengan asumsi fungsi "keras" ada (untuk berbagai definisi "keras"), kita dapat membuat generator pseudorandom.

Dana Moshkovitz
sumber