Musuh Tidak Seragam vs. Seragam

Pertanyaan ini muncul dalam konteks kriptografi, tetapi di bawah ini saya akan menyajikannya dalam hal teori kompleksitas, karena orang-orang di sini lebih mengenal yang terakhir. Pertanyaan ini terkait dengan Masalah dalam NP tetapi tidak dalam Average-P / poly dan Beating Nonuniformity oleh Oracle Access .

Pernyataan tidak resmi: Kapan musuh yang tidak seragam (mis. Keluarga rangkaian ukuran-poli) berhasil mematahkan skema kriptografi, tetapi musuh yang seragam (mis. Mesin Turing waktu-poli yang probabilistik) tidak?

Pernyataan kompleksitas-teori: Ini tidak persis sama dengan pernyataan informal di atas, tetapi saya sebenarnya tertarik dengan versi ini:

Apa masalah alami yang ada di ?$(\mathsf{NP} \cap \mathsf{P/poly}) - \mathsf{AvgP}$

Dengan kata lain, masalah alami yang sulit rata-rata apa yang dapat diselesaikan oleh rangkaian keluarga berukuran-poli?$\mathsf{NP}$

Kata diselesaikan dapat diartikan sebagai kasus terburuk atau rata-rata (yang terakhir lebih disukai).

Jika masalah alami tidak dapat ditemukan dengan mudah, masalah buatan juga dapat diterima.

Hampir tidak ada masalah alami yang diyakini ada di P / poly tetapi tidak di P. Contoh-contoh buatan dapat diadaptasi untuk menjawab pertanyaan Anda.

Asumsikan , maka ada bahasa L unary dalam NP yang tidak dalam P - unary berarti bahwa semua string dalam bahasa memiliki bentuk untuk beberapa n.$E \neq NE$$1^n$

Kemudian tentukan L 'menjadi himpunan semua string x sedemikian sehingga adalah dalam L. Ini adalah dalam NP, itu dalam P / poli, dan itu bukan dalam waktu polinomial rata-rata$1^{length(x)}$