Apa yang dimaksud dengan argumen fisika statistik heuristik?

Saya telah mendengar bahwa ada argumen heuristik dalam fisika statistik yang menghasilkan hasil dalam teori probabilitas di mana bukti yang kuat tidak diketahui atau sangat sulit untuk dicapai. Apa contoh mainan sederhana dari fenomena seperti itu?

Akan lebih baik jika jawabannya diasumsikan sedikit latar belakang dalam fisika statistik dan dapat menjelaskan apa heuristik misterius ini dan bagaimana mereka dapat dibenarkan secara informal. Juga, mungkin seseorang dapat menunjukkan gambaran luas tentang seberapa banyak heuristik ini dapat dibenarkan secara ketat dan bagaimana program Lawler, Schramm dan Werner cocok dengan ini.

Paragraf kedua dari tanggapan RJK patut lebih detail.

Biarkan menjadi rumus dalam bentuk konjungtif normal, dengan m klausa, n variabel, dan paling banyak k variabel per klausa. Misalkan kita ingin menentukan apakah memiliki tugas yang memuaskan. Formula adalah turunan dari masalah keputusan k-SAT.ϕ $\phi$$\phi$$\phi$

Ketika ada beberapa klausa (jadi m cukup kecil dibandingkan dengan n), maka hampir selalu mungkin untuk menemukan solusi. Algoritma sederhana akan menemukan solusi dalam waktu linear kira-kira dalam ukuran formula.

Ketika ada banyak klausa (jadi m cukup besar dibandingkan dengan n), maka hampir selalu demikian bahwa tidak ada solusi. Ini dapat ditunjukkan dengan argumen penghitungan. Namun, selama pencarian hampir selalu mungkin untuk memangkas sebagian besar ruang pencarian dengan menggunakan teknik konsistensi, karena banyak klausa berinteraksi begitu luas. Membangun ketidakpuasan biasanya dapat dilakukan secara efisien.

• V. Chvátal dan B. Reed. Mick mendapat beberapa (kemungkinan ada di pihaknya) , FOCS 1992. doi: 10.1109 / SFCS.1992.267789

Pada tahun 1986 Fu dan Anderson memperkirakan hubungan antara masalah optimisasi dan fisika statistik, berdasarkan sistem spin glass. Meskipun mereka menggunakan kalimat suka

Secara intuitif, sistem harus cukup besar, tetapi sulit untuk lebih spesifik.

mereka benar-benar memberikan prediksi spesifik.

• Y Fu dan PW Anderson. Penerapan mekanika statistik untuk menyelesaikan masalah NP dalam optimisasi kombinatorial , J. Phys. A. 19 1605, 1986. doi: 10.1088 / 0305-4470 / 19/9/033

Berdasarkan argumen dari fisika statistik, Zecchina dan kolaborator menduga bahwa k-SAT akan menjadi sulit ketika mendekati nilai kritis. Nilai kritis yang tepat tergantung pada k, tetapi berada di wilayah 3,5 hingga 4,5 untuk 3-SAT.$\alpha = m/n$

• Rémi Monasson, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman, Lidror Troyansky. Menentukan kompleksitas komputasi dari karakteristik `transisi fase ' , Nature 400 133–137, 1999. ( doi: 10.1038 / 22055 , versi gratis )

Friedgut memberikan bukti yang kuat tentang argumen heuristik ini. Untuk setiap nilai tetap k, ada dua ambang batas . Untuk bawah , ada tugas yang memuaskan dengan probabilitas tinggi. Untuk nilai atas , rumus tidak memuaskan dengan probabilitas tinggi. α α 1 α α 2$\alpha_1 < \alpha_2$$\alpha$$\alpha_1$$\alpha$$\alpha_2$$\phi$

• Ehud Friedgut (dengan lampiran oleh Jean Bourgain), ambang batas tajam properti grafik, dan masalah sat$k$ , J. Amer. Matematika Soc. 12 1017-1054, 1999. ( PDF )

Dimitris Achlioptas bekerja pada banyak masalah yang tersisa, dan menunjukkan bahwa argumen di atas berlaku untuk masalah kepuasan kendala juga. Ini diizinkan untuk menggunakan lebih dari dua nilai untuk setiap variabel. Satu makalah utama menunjukkan dengan seksama mengapa algoritma Survey Propagation bekerja sangat baik untuk menyelesaikan instance k-SAT acak.

• A. Braunstein, M. Mézard, R. Zecchina, Perbanyakan survei: Algoritma untuk kepuasan , Struktur & Algoritma Acak 27 201–226, 2005. doi: 10.1002 / rsa.20057
• D. Achlioptas dan F. Ricci-Tersenghi, Tentang Solusi-Geometri Ruang dari Masalah Kepuasan Kendala Acak , STOC 2006, 130–139. ( pracetak )

Ada survei terbaru oleh Lawler tentang SLE . Anda harus mengetahui sedikit analisis yang rumit.

Meskipun tidak secara langsung terkait dengan pertanyaan Anda, mungkin Anda dapat memeriksa beberapa makalah Achlioptas yang juga sesuai di bawah payung "formalisasi fisikawan heuristik", meskipun dari sudut pandang seorang ilmuwan komputer teoretis. Atau mungkin lebih jauh ke dalam perspektif statphys yang bisa Anda telusuri melalui beberapa karya Zecchina .

Saya pikir perlu menambahkan bahwa apa yang Anda sebut sebagai "hasil" fisikawan - yang sebagian besar harus disebut dugaan - dalam kategori masalah yang sangat luas ini bergantung hampir sama (atau bahkan lebih) pada eksperimen numerik seperti ( daripada) pada argumen heuristik.

(memperluas komentar saya)

"Intuisi fisik" di balik metode statistik, seperti yang digunakan dalam perhitungan, adalah Maximum Entropy (a-la Jaynes) ditambah metode stokastik terkait seperti Simulated Annealing atau Deterministic Annealing . Jaynes merumuskan pendekatan entropi maksimum ( generalisasi langsung dari fisika statistik), untuk mengatasi masalah terbalik (dalam istilah komputasi ini termasuk masalah )$NP$

Sebuah survei " heuristik dari alam " dapat ditemukan di sini (sekitar 95)

Heuristik lain melibatkan langrangians umum (alias algoritma primal-dual / expectation-maximization)

Namun ini tidak menguras semua " heuristik dari alam " seperti pada kenyataannya dari 2003 dan heuristik baru berdasarkan electromargnetism telah digunakan untuk menangani kedua metode optimasi kontinu dan diskrit / kombinatorial (seperti ransel multidimensi , atau TSP , sekitar 2012)