Contoh transisi fase kekerasan

Misalkan kita memiliki masalah yang diparameterisasi dengan p-parameter bernilai riil yang "mudah" untuk dipecahkan ketika dan "hard" ketika untuk beberapa nilai , . p = p 1 p 0 p $p=p_0$$p=p_1$$p_0$$p_1$

Salah satu contohnya adalah menghitung konfigurasi putaran pada grafik. Menghitung pewarnaan yang tepat, set independen, subgraph Euler sesuai dengan fungsi partisi masing-masing model hardcore, Potts dan Ising, yang mudah diperkirakan untuk "suhu tinggi" dan sulit untuk "suhu rendah". Untuk MCMC sederhana, transisi fase kekerasan sesuai dengan titik di mana waktu pencampuran melompat dari polinomial ke eksponensial ( Martineli, 2006 ).

Contoh lain adalah inferensi dalam model probabilistik. Kami "menyederhanakan" model yang diberikan dengan mengambil , kombinasi itu dengan model "semua variabel independen". Untuk masalahnya adalah sepele, untuk itu tidak bisa diatasi, dan ambang kekerasan berada di antara keduanya. Untuk metode inferensi paling populer, masalah menjadi sulit ketika metode gagal untuk bertemu, dan titik ketika itu terjadi sesuai dengan transisi fase (dalam arti fisik) dari distribusi Gibbs tertentu ( Tatikonda, 2002 ).p p = 1 p = $1-p$$p$$p=1$$p=0$

Apa contoh menarik lainnya dari "lompatan" kekerasan karena beberapa parameter kontinu bervariasi?

Motivasi: untuk melihat contoh "dimensi" kekerasan lain selain tipe grafik atau tipe logika

Dalam perkiraan kasus terburuk standar, ada banyak ambang tajam karena faktor perkiraan bervariasi.

Sebagai contoh, untuk 3LIN, memuaskan sebanyak yang diberikan persamaan linear Boolean pada masing-masing 3 variabel, ada algoritma pendekatan tugas acak sederhana untuk pendekatan 1/2, tetapi setiap perkiraan lebih baik daripada beberapa t = 1/2 + o (1) sudah sekeras SAT (diperkirakan membutuhkan waktu eksponensial).

Saya tidak yakin apakah ini adalah jenis masalah yang Anda cari, tetapi fase transisi dari masalah NP-Complete adalah fenomena yang sudah dikenal. Lihat artikel Brian Hayes "Can't Get No Satisfaction" tentang transisi fase 3-SAT dan "Masalah Paling Mudah" tentang transisi Fase Partisi Fase, untuk beberapa artikel populer tentang masalah ini.

Selman dan Kirkpatrick pertama kali menunjukkan secara numerik bahwa transisi fase untuk 3-SAT adalah ketika rasio klausa terhadap variabel berada di sekitar 4,3.

Gent dan Walsh pertama kali menunjukkan secara numerik bahwa transisi fase untuk Masalah Partisi Angka terjadi ketika rasio bit terhadap panjang daftar adalah sekitar 1. Kemudian ini dibuktikan secara analitis oleh Borgs, Chayes dan Pittel .

Travelling Salesman, Grafik Pewarnaan, Hamiltonian Cycle, di antara yang lain, juga tampaknya memiliki transisi fase untuk parameterisasi yang cocok untuk pembuatan instance masalah. Saya pikir aman untuk mengatakan bahwa itu adalah kepercayaan umum bahwa semua masalah NP-Complete menunjukkan transisi fase untuk parameterisasi yang sesuai.

Terkait dengan (beberapa) model kebisingan untuk perhitungan kuantum adalah nilai ambang batas untuk tingkat kebisingan, di atas mana gerbang bising dapat disimulasikan oleh gerbang Clifford, sehingga proses perhitungan kuantum menjadi dapat disimulasikan secara efisien. Sebagai permulaan, lihat Plenio dan Virmani, Batas atas pada ambang toleransi kesalahan dari komputer kuantum berbasis Cli-ord yang berisik (arXiv: 0810.4340v1).

Model yang dapat dipecahkan seperti ini memberi tahu kami mengenai masalah praktis yang ada di mana-mana: untuk sistem kuantum fisik tertentu yang bersentuhan dengan reservoir termal (mungkin pada suhu nol), adalah tingkat kebisingan yang terkait dengan reservoir termal di bawah atau di atas ambang batas untuk simulasi efisien dengan klasik sumber daya? Jika yang terakhir, algoritma simulasi apa yang optimal?

$k$$k$$k$

$f(k)$$k$$f(k)$$2^k$$k$$1 \le f(k) < 2^k$

$k$$n$$k$$f(k)/2^k$

$f(k)$$f(k)+1$

• Jan Kratochvíl, Petr Savický dan Zsolt Tuza, Satu Lagi Kejadian Variabel Membuat Kepuasan Lompat dari Sepele ke Lengkap-NP , SIAM J. Comput. 22 (1) 203-210, 1993. doi: 10.1137 / 0222015

$f(k)$$f(k) = \Theta(2^k/k)$

• Heidi Gebauer, Menolak dugaan lingkungan dengan implikasi pada SAT , Combinatorica 32 (5) 573-587, 2012. doi: 10.1007 / s00493-012-2679-y (pracetak)
• Heidi Gebauer, Tibor Szabó, Gábor Tardos, Lemma lokal sangat cocok untuk SAT , SODA 2011.