Apakah algoritma acak konstruktif?

Dari, pembuktian dengan metode probabilistik sering dikatakan tidak konstruktif.

Namun, bukti dengan metode probabilistik memang merancang algoritma acak dan menggunakannya untuk membuktikan keberadaan. Dikutip dari p103 Randomized Algorithms Oleh Rajeev Motwani, Prabhakar Raghavan :

Kita bisa melihat buktinya dengan metode probabilistik sebagai algoritma acak. Ini kemudian akan memerlukan analisis lebih lanjut yang membatasi probabilitas bahwa algoritma gagal menemukan partisi yang baik pada eksekusi yang diberikan. Perbedaan utama antara eksperimen pemikiran dalam metode probabilistik dan algoritma acak adalah akhir yang dihasilkan masing-masing. Ketika kita menggunakan metode probabilistik, kita hanya peduli dengan menunjukkan bahwa objek kombinatorial ada; dengan demikian, kami puas dengan menunjukkan bahwa peristiwa yang menguntungkan terjadi dengan probabilitas yang tidak nol. Dengan algoritma acak, di sisi lain, efisiensi adalah pertimbangan penting - kita tidak bisa mentolerir probabilitas keberhasilan yang sangat kecil.

Jadi saya bertanya-tanya apakah algoritma acak dipandang tidak konstruktif, meskipun mereka menghasilkan solusi pada akhir setiap proses, yang mungkin atau mungkin bukan solusi ideal.

Bagaimana mendefinisikan algoritme atau bukti "konstruktif"?

Terima kasih!

Metode probabilistik biasanya digunakan untuk menunjukkan bahwa probabilitas beberapa objek acak memiliki properti tertentu adalah nol, tetapi tidak menunjukkan contoh apa pun. Itu menjamin bahwa algoritma "repeat-hingga-success" akhirnya akan berakhir, tetapi tidak memberikan batas atas pada runtime. Jadi, kecuali kemungkinan kepemilikan properti adalah substansial, bukti keberadaan dengan metode probabilistik membuat algoritma yang sangat buruk.

Pada kenyataannya, algoritma probabilistik sebenarnya bukan bukti keberadaan yang konstruktif, sama seperti algoritma untuk menghasilkan bukti keberadaan yang konstruktif. Keluaran adalah objek dari jenis yang dimaksudkan untuk membuktikan keberadaan; tetapi fakta bahwa pada akhirnya akan menghasilkan satu ("akan ada iterasi di mana ia menghasilkan contoh - kecuali dengan probabilitas nol ...") tidak cukup untuk menjadi konstruktif; itu hanya akan memuaskan bagi seseorang yang sudah menerima bahwa non-nol-probabilitas-tanpa-konstruksi cukup untuk keberadaan. Sebaliknya, jika Anda memiliki ikatan yang baik pada run-time, maka pada prinsipnya tidak ada alasan untuk tidak menjalankannya untuk benar-benar menghasilkan contoh. Algoritma probabilistik yang baik masih bukan bukti yang konstruktif, tetapi yang baikberencana untuk mendapatkan bukti konstruktif.

Perhatikan bahwa ide ini, bahwa algoritma acak adalah strategi bukti (sebagai lawan dari bukti itu sendiri) untuk menunjukkan kuantifikasi eksistensial, tidak berbeda dengan gagasan bahwa induksi adalah strategi bukti yang baik untuk menunjukkan kuantifikasi universal (lebih dari bilangan asli) ). Analogi ini mungkin tampak menarik, karena induksi pada dasarnya adalah jantung rekursi sebagai teknik komputasi. (Untuk bilangan bulat positif , jika Anda ingin memutuskan apakah adalah jumlah dari angka ganjil berturut-turut sebelum , Anda dapat mengurangi ini untuk menyelidiki apakah adalah jumlah ganjil berturut-turut angka sebelum$n$$n^2$$2n+1$$(n-1)^2$$2n-1$, dan lain-lain.) Induksi pada dasarnya adalah strategi pembuktian algoritmik yang telah kami angkat menjadi teorema, yang memungkinkan kami untuk memiliki pengetahuan tanpa secara eksplisit menghitungnya setiap waktu. Namun, induksi diterima secara konstruktif karena sudah merupakan aksioma (-skema) aritmatika Peano, dan yang tidak tergantung pada aksioma lainnya. Sebaliknya, tidak ada aturan inferensi atau aksioma yang memungkinkan metode probabilistik untuk membuktikan keberadaan secara konstruktif, atau untuk membuktikan secara konstruktif bahwa algoritma probabilistik menghasilkan bukti keberadaan, atau apa pun di sepanjang garis ini. Anda tidak bisa membuktikan bahwa ada contoh kelas objek dari fakta bahwa ada algoritma probabilistik untuk membangunnya, kecuali jika Anda sudah menerima proposisi itu, baik sebagai aksioma, atau dari tempat lain.

Tentu saja, orang mungkin mengadopsi posisi filosofis antara dengan konstruktivisme dan pendekatan klasik untuk eksistensi, dan mengatakan bahwa apa yang diinginkannya bukanlah konstruksi semata, melainkan skema konstruksi yang dibiarkan gagal dengan probabilitas kurang dari satu; yang akan membuat konstruksi probabilistik "skematis", jika tidak sepenuhnya konstruktif. Di mana orang ingin menarik garis, untuk mengatakan bahwa mereka menemukan bukti keberadaan "memuaskan", pada akhirnya tergantung pada seberapa banyak intuisi (dalam arti non-filosofis) yang ingin mereka peroleh dari bukti.

Kompleksitas bukti seragam adalah bidang yang dikhususkan (antara lain) untuk mempelajari gagasan konstruktif bukti, dan hubungannya dengan kelas kompleksitas. Untuk masing-masing kelas kompleksitas sirkuit (seragam) yang populer, seseorang dapat mendefinisikan sebuah teori di mana segala sesuatu yang dapat dibuktikan memiliki "dukungan" dalam suatu algoritma dalam kelas kompleksitas ini. Algoritma acak ditampung melalui versi prinsip pigeonhole (anehnya).

Sayangnya saya bukan ahli jadi saya tidak bisa mengatakan lebih banyak, selain mengarahkan Anda ke buku oleh Cook dan Nguyen (Cook yang sama seperti dalam teorema Cook) dan untuk karya Emil Jeřábek , terutama tesisnya tentang perhitungan acak.