Apa contoh bagaimana ketidakseragaman dapat bermanfaat?

Saya ingin tahu tentang cara di mana Anda telah melihat ketidakseragaman berguna dalam perhitungan. Salah satu caranya adalah keacakan, seperti dalam , dan yang lainnya adalah tabel pencarian yang digunakan untuk menunjukkan bahwa semua bahasa memiliki sirkuit yang tidak seragam.$BPP \subseteq P/poly$

Secara khusus, saya tertarik pada cara-cara agar objek diketahui ada melalui metode probabilistik dan metode bukti non-konstruktif (atau tidak cukup konstruktif) lainnya dapat dimanfaatkan dengan menggunakan ketidak-seragaman. Saya lebih suka contoh-contoh itu alami, bukan dibuat-buat. Untuk menjadi jelas, rangkaian untuk masalah yang dibuat bisa menjadi seperti: diberikan beberapa bahasa , saya membuat sirkuit ukuran polinomial dengan menghitung beberapa fungsi yang sangat sulit f ( | x | ) menggunakan saran saya dan menanyakan apakah f ( | x | ) n / | f ( | x | ) $L \in P$$f(|x|)$ .$f(|x|)^{n/|f(|x|)|} \oplus x \in L$

Contoh saya seperti adalah argumen bahwa dengan menghitung string dalam bahasa (lihat misalnya https://blog.computationalcomplexity.org/2004/01/little-theorem.html ) .$\mathrm{NE\subseteq coNE}/(n+1)$

Salah satu contohnya adalah . Teorema ini dibuktikan oleh Reinhardt dan Allender dalam makalah mereka "Making Nondeterminism Unambiguous" . Tanpa membahas rinciannya, saran dalam algoritme mereka terdiri dari urutan penugasan tepi-berat sehingga untuk setiap digraf G yang disandikan oleh string n- bit, beberapa penugasan dalam urutan membuat G "min-unique". Urutan seperti itu dapat terbukti ada dengan metode probabilistik. Kontribusi utama Reinhardt dan Allender adalah untuk memberikan algoritma ruang-log yang tidak ambigu untuk menentukan tugas yang mana dalam urutan yang bekerja untuk digraf $\mathbf{NL} \subseteq \mathbf{UL}/\text{poly}$$G$$n$$G$$G$dan untuk memutuskan konektivitas - t pada digraf min-unik.$s$$t$

Seperti , itu menduga bahwa nonuniformity sebenarnya tidak diperlukan di sini, yaitu, itu menduga bahwa N L = U L .$\mathbf{BPP} \subseteq \mathbf{P}/\text{poly}$$\mathbf{NL} = \mathbf{UL}$

Saya tidak yakin apakah itu sesuai dengan apa yang Anda cari, tetapi ada beberapa hasil yang membuktikan teorema hierarki untuk kelas kompleksitas semantik dengan sedikit nasihat, di mana tidak ada teorema hierarki yang diketahui tanpa saran. Contoh paling terkenal adalah BPP, yang kita tidak tahu teorema hierarki, tetapi Fortnow dan Santhanam menunjukkan satu ada dengan sedikit nasihat (membangun pada hasil dari Barak yang menggunakan lebih banyak saran). Artikel oleh Melkebeek dan Pervyshev ini memberikan referensi dan sejarah, dan teorema yang tampaknya merangkum yang sebelumnya.