Seberapa umum transisi fase dalam masalah NP-complete?

Telah diketahui bahwa banyak masalah NP-lengkap menunjukkan fase transisi. Saya tertarik di sini dalam transisi fase sehubungan dengan pengungkungan dalam bahasa, daripada kekerasan input, relatif terhadap suatu algoritma.

Untuk membuat konsep ini ambigu, mari kita secara resmi mendefinisikannya sebagai berikut. Suatu bahasa $L$ menunjukkan transisi fase (sehubungan dengan penahanan), jika

1. Ada parameter pesanan $r(x)$ , yang merupakan fungsi waktu yang dihitung secara polinomial, yang bernilai nyata dari instance.

2. Ada ambang batas $t$ . Entah itu konstanta nyata, atau mungkin bergantung pada $n=|x|$, yaitu, $t=t(n)$ .

3. Untuk hampir setiap $x$ dengan $r(x)<t$ , kita memiliki $x\in L$ . ( Hampir setiap sarana di sini: semuanya tapi hampir semuanya, yaitu, proporsi mendekati 1, seperti $n\rightarrow\infty$ ).

4. Untuk hampir setiap $x$ dengan $r(x)>t$ , kita memiliki $x\notin L$ .

5. Untuk hampir setiap $x$ , ia menyatakan bahwa $r(x)\neq t$ . (Yaitu, wilayah transisi "sempit.")

Banyak masalah NP-lengkap alami menunjukkan transisi fase dalam pengertian ini. Contohnya adalah banyak varian SAT, semua properti grafik monoton, berbagai masalah kepuasan kendala, dan mungkin banyak lainnya.

Pertanyaan: Apa saja pengecualian "baik"? Apakah ada masalah NP-complete alami, yang (mungkin) tidak memiliki fase transisi dalam arti di atas?

Peneliti ahli dalam bidang ini pada dasarnya menyatakan bahwa transisi fase adalah fitur universal dari masalah lengkap NP meskipun ini belum diformulasikan / dibuktikan secara ketat dan belum secara luas dianggap / disebarluaskan di bidang yang lebih besar (itu lebih banyak berasal dari yang berorientasi empiris. cabang studi). ini hampir merupakan dugaan terbuka. ada bukti kuat. tidak ada kandidat yang masuk akal untuk menyelesaikan masalah NP non fase transisi. berikut adalah dua referensi yang mendukung pov ini:

• Transisi fase dalam masalah NP-lengkap: tantangan untuk probabilitas, kombinatorik, dan ilmu komputer / Moore

• Perilaku transisi fase / Walsh (ppt)

di sini adalah sketsa kasar dari kebenaran pernyataan itu. itu ada hubungannya dengan P yang terkandung dalam NP lengkap. masalah / bahasa lengkap NP harus memiliki instance yang dapat dipecahkan dalam waktu P dan yang lainnya dipecahkan dalam waktu eksponensial (atau setidaknya superpolinomial-) jika P ≠ NP. tetapi harus selalu ada cara untuk "mengelompokkan" instance P dari instance "non-P". oleh karena itu harus selalu ada beberapa "kriteria transisi" antara instance P dan non-P. singkatnya, mungkin fenomena ini secara intris ditambah dengan P ≠ NP!

argumen kasar lainnya: semua masalah lengkap NP dapat dipertukarkan melalui pengurangan. jika transisi fase ditemukan dalam satu, itu harus ditemukan di semuanya.

bukti yang lebih mendalam untuk ini, baru-baru ini (~ 2010) ditunjukkan transisi fase muncul untuk batas bawah pada sirkuit monoton untuk deteksi klik pada grafik acak.

• Kompleksitas kasus rata-rata untuk mendeteksi klik / Rossman

pengungkapan penuh: Moshe Vardi telah mempelajari transisi fase khususnya di SAT dan memiliki pandangan yang lebih skeptis yang kontras dalam pembicaraan / video ini.

• Transisi fase dan kompleksitas komputasi

$G_{n,m}$$n$$m$$\binom{n}{2}$$m$$G_{n,m}$

C pewarnaan D grafik biasa memiliki serangkaian transisi Discrete, tidak secara bertahap, kecuali Anda melakukan peregangan.

Ini adalah tabel hasil pewarnaan, yang akan saya kirimkan ke SAT17. Perhatikan bahwa 3 pewarnaan dari 6 grafik biasa tidak mungkin kecuali untuk beberapa contoh. Demikian juga 4 pewarnaan grafik derajat kesepuluh ... Grafik C3D5N180 agak sulit. C4D9 Golden Point hanya sementara pada C4D9N180; Grafik C4D9 adalah 4cnfs terberat berdasarkan ukuran yang saya temui, jadi C4D9 memenuhi syarat sebagai "Tempat Keras". Titik Emas C5D16 diduga ada, tetapi akan berada di wilayah hard spot dari 5 pewarnaan hingga 6 pewarnaan.

          Universal Constants of Regular Graph Coloring

Rumus pewarnaan memiliki variabel lgC per simpul, untuk total variabel lgC * N; tepi memiliki klausa pewarnaan C, untuk total klausa C * M. Ada beberapa klausa tambahan per titik untuk menyingkirkan warna tambahan. Poin Emas adalah N terkecil sehingga: Colorability C pada grafik derajat D dengan simpul N hampir selalu memuaskan, dengan probabilitas mendekati 1. Untuk Probabilitas Tinggi, N contoh acak yang memuaskan. Untuk Sangat Tinggi, N * N memuaskan. Untuk Super High, N * N * N kejadian acak memuaskan.

Poin pewarnaan emas Probabilitas Tinggi (1 - 1 / N) adalah:

C3D5N180 C4D6N18 C4D7N35 C4D8N60 C4D9N180? C5D10N25 C5D11N42 C5D12N72

Poin pewarnaan emas yang sangat tinggi (1 - 1 / (N * N)) adalah:

C3D5N230? C4D6N18 C4D7N36 C4D8N68 C4D9N ??? C5D10N32 C5D11N50 C5D12N78

Poin pewarnaan Super High (1 - 1 / (N * N * N)) adalah:

C3D5N ??? C4D6N22 C4D7N58 C4D8N72? C4D9N ??? C5D10N38 C5D11N58 C5D12N ??

Semua contoh acak dalam penelitian ini memuaskan. Poin probabilitas linier memeriksa ratusan formula yang memuaskan. Poin probabilitas kuadratik memeriksa puluhan ribu rumus yang memuaskan. Poin probabilitas kubik memeriksa ratusan ribu formula yang memuaskan. Poin C4D9 dan C5D13 sulit. Titik C5D16 diduga ada. Satu contoh acak enam tingkat enam belas berwarna akan membuktikan dugaan itu.