Status Dunia Impagliazzo?

Pada 1995, Russell Impagliazzo mengusulkan lima dunia kompleksitas:

1- Algorithmica: dengan semua konsekuensi luar biasa.$P=NP$

2- Heuristica: Masalah lengkap sulit pada kasus terburuk ( ) tetapi dipecahkan secara efisien dalam kasus rata-rata.$NP$$P \ne NP$

3- Pessiland: Ada masalah -kasus rata-rata lengkap tetapi fungsi satu arah tidak ada. Ini menyiratkan bahwa kita tidak dapat membuat contoh sulit dari masalah lengkap dengan solusi yang diketahui. $NP$$NP$

4- Minicrypt: Ada fungsi satu arah tetapi sistem kriptografi kunci publik tidak mungkin

5- Cryptomania: Ada sistem kriptografi kunci publik dan komunikasi yang aman dimungkinkan.

Dunia mana yang disukai oleh kemajuan terbaru dalam kompleksitas komputasi? Apa bukti terbaik untuk pilihan itu?

Russell Impagliazzo, Pandangan Pribadi tentang Kompleksitas Kasus Rata-rata , 1995

Lima Dunia Impagliazzo, blog Kompleksitas Komputasi

Sekitar setahun yang lalu saya ikut menyelenggarakan lokakarya tentang kompleksitas dan kriptografi: status dunia Impagliazzo , dan slide serta video di situs web mungkin menarik.

Jawaban singkatnya adalah bahwa tidak banyak yang berubah dalam arti bahwa sebagian besar peneliti masih percaya bahwa kita hidup di "Cryptomania" dan kita masih memiliki kurang lebih bukti yang sama untuk ini, dan tidak banyak kemajuan dalam meruntuhkan salah satu dunia untuk satu sama lain.

Mungkin informasi baru yang paling signifikan adalah algoritma Shor yang menunjukkan bahwa setidaknya jika Anda mengganti P dengan BQP, cryptosystem kunci publik yang paling umum digunakan tidak aman. Tetapi, karena cryptosystems berbasis Lattice, asumsi default adalah bahwa kita hidup dalam cryptomania bahkan dalam kasus ini, meskipun mungkin konsensus di sini sedikit lebih lemah daripada kasus klasik. Bahkan dalam kasus klasik, tampaknya ada lebih banyak bukti untuk keberadaan fungsi satu arah ("Minicrypt") daripada keberadaan enkripsi kunci publik ("Cryptomania"). Namun, mengingat upaya yang telah dihabiskan orang dalam mencoba memecahkan berbagai cryptosystem kunci publik, ada bukti signifikan untuk yang kedua juga.

Pertanyaan bagus, tetapi ilmuwan bahkan belum dapat memisahkan "Algorithmica" dari kasus-kasus yang tersisa, apalagi memutuskan dunia tempat kita hidup sekarang.

Yang mengatakan, ada beberapa makalah penelitian tentang masalah ini. Lihat misalnya: Pada kemungkinan mendasarkan Kriptografi pada asumsi bahwa P! = NP oleh Goldreich dan Goldwasser, dan rujukannya.

Lihat juga Pada mendasarkan fungsi satu arah pada NP-hardness oleh Adi Akavia et al.

Selain itu, diketahui bahwa mendekode beberapa cryptosystem adalah NP-hard (Lihat, misalnya, cryptosystem McEliece , atau kriptografi berbasis Lattice ). Saya tidak tahu mengapa ini TIDAK menyelesaikan masalah, karena saya tidak terbiasa dengan cryptosystems seperti itu. Lihat komentar Peter Shor di bawah ini.

Saya juga menyarankan Anda melihat diskusi di Stackoverflow . Meninjau literatur yang mengutip karya Impagliazzo juga bisa menjadi pelajaran.

EDIT: Hasil berikut mungkin menarik:

Feigenbaum dan Fortnow. Random-Self-Reducibility dari Set Lengkap. Jurnal SIAM tentang Komputer, 22: 994-1005, 1993.

Bogdanov dan Trevisan. Pada Pengurangan Kasus Terburuk ke Kasus Rata-rata untuk Masalah NP. Dalam Prosiding Simposium IEEE Tahunan ke-44 tentang Yayasan Ilmu Komputer, halaman 308–317, 2003.

Akavia, Goldreich, Goldwasser, dan Moshkovitz. Pada Mendasarkan Fungsi Satu Arah pada NP-Hardness

Gutfreund dan Ta-Shma. Koneksi baru antara derandomisasi, kompleksitas kasus terburuk dan kompleksitas kasus rata-rata. Tech. Rep. TR06-108, Kolokium Elektronik tentang Kompleksitas Komputasi, 2006.

Bogdanov dan Trevisan. Kompleksitas kasus rata-rata. Ditemukan. Tren Theor. Komputasi. Sci. 2, 1 (Oktober 2006), 1-106. DOI = http://dx.doi.org/10.1561/0400000004