Adakah masalah NP yang diketahui yang diperkirakan sulit secara eksponensial?

ETH menyatakan bahwa SAT tidak dapat diselesaikan dalam kasus terburuk dalam waktu subeksponensial. Bagaimana dengan kasus rata-rata? Apakah ada masalah alami dalam NP yang diperkirakan sulit secara eksponensial dalam kasus rata-rata?

Ambil kasus rata-rata berarti waktu berjalan rata-rata dengan distribusi seragam pada input.

$2^{n^{1-o(1)}}$$2^{O(n/\log n)}$

$n$$cn$$c$

Ada beberapa generator nomor psuedorandom yang kami tidak memiliki algoritma waktu polinomial untuk dipecah. Saya kira Anda bisa menganggap mereka sulit pada kasus rata-rata. Lihat generatornya di www.ecrypt.eu.org/stream/ Tentu saja ada yang lain, Anda dapat meneliti sebagian besar dari mereka secara online.

Pemahaman saya adalah bahwa meskipun ada beberapa kandidat dari teori unbreakability of cryptography dan generator angka acak [misalnya beberapa yang dikutip dalam Razborov / Rudich, Natural Proofs], sebagian besar aspek dari pertanyaan Anda diakui pada dasarnya pertanyaan kunci "masih terbuka" oleh para ahli di lapangan. dari pengantar survei komprehensif, Average Case Complexity oleh Bogdanov dan Trevisan (2006) memiliki beberapa poin terkait. Ceramah Trevisan tentang penemuan dan pertanyaan terbuka tentang kompleksitas kasus rata-rata juga dapat membantu.

$\neq$

$\neq$

Teknik yang tepat untuk menerapkan teori semacam itu untuk masalah dan distribusi alami belum ditemukan. Dari sudut pandang ini, keadaan saat ini dari teori kompleksitas kasus rata-rata dalam NP mirip dengan keadaan teori tidak dapat diperkirakan masalah optimasi NP sebelum Teorema PCP.