Fungsi monoton acak

Dalam makalah Natural Proofs karya Razborov-Rudich , halaman 6, pada bagian yang mereka bahas bahwa ada "bukti lowerbound yang kuat terhadap model sirkuit monoton " dan bagaimana mereka masuk dalam gambar, ada kalimat-kalimat berikut:

Di sini masalahnya bukan konstruktif - sifat-sifat yang digunakan dalam bukti-bukti ini semuanya layak - tetapi tampaknya tidak ada analog formal yang bagus dari kondisi luasnya. Secara khusus, tidak ada yang merumuskan definisi yang bisa diterapkan dari "fungsi monoton acak."

Bukankah mudah untuk membedakan output dari fungsi monoton dari string acak? Bukankah keberadaan lowerbound yang kuat memberi tahu kita bahwa tidak ada hal seperti itu?

Pertanyaanku adalah:

Apa yang mereka maksud dengan definisi yang bisa diterapkan dari "fungsi monoton acak" ?

Saya tidak yakin, tapi saya pikir masalahnya di sini adalah fakta bahwa kami tidak memiliki asumsi kuat tentang generator fungsi monoton pseudorandom (setidaknya tidak ada yang saya tahu). Gagasan pembuktian dalam makalah Razborov-Rudich adalah sebagai berikut:

jika ada sifat alami dari fungsi (yaitu properti yang dapat ditentukan secara efisien yang menampung subset fungsi yang cukup besar dan menyiratkan bahwa fungsi tersebut memerlukan sirkuit besar), maka ia dapat digunakan untuk memecah generator fungsi pseudorandom (yang juga memecah generator pseudorandom dan satu fungsi jalan).

Jika kita menyatakan kembali teorema dalam hal fungsi monoton dan sirkuit monoton, kami ingin mengatakannya

jika ada properti alami fungsi monoton (yaitu properti yang dapat ditentukan secara efisien yang menampung subset fungsi monoton yang cukup besar dan menyiratkan bahwa fungsi tersebut memerlukan sirkuit monoton besar ), maka ia dapat digunakan untuk memecah generator fungsi pseudorandom (yang memecah juga pseudorandom generator dan fungsi satu arah),

tetapi sekarang bukti dari kertas berhenti bekerja, karena generator pseudorandom kami mengeluarkan fungsi umum, tidak harus yang monoton, dan kami tidak dapat menggunakan properti alami kami untuk memecahkannya, karena bahkan subset fungsi monoton yang relatif besar tidak akan besar relatif terhadap fungsi umum, untuk himpunan fungsi monoton itu sendiri tidak besar relatif terhadap himpunan semua fungsi ( http://en.wikipedia.org/wiki/Dedekind_number ). Kita dapat mendefinisikan beberapa generator fungsi monoton pseudorandom dan menggunakan properti alami untuk memecahkannya, tetapi kita mungkin tidak akan memiliki kesetaraan antara generator ini dan fungsi satu arah, sehingga teorema tidak akan begitu menarik.

Mungkin kesulitan ini dapat diperbaiki (tapi saya tidak berpikir itu mengikuti dari bukti di koran dengan cara langsung) dan mungkin masalah dengan fungsi monoton terletak di tempat lain. Saya benar-benar ingin seseorang yang lebih berpengalaman daripada saya untuk mengkonfirmasi jawaban saya atau untuk menunjukkan di mana saya salah.