Apakah "Di mana masalah yang sangat sulit" bertahan? Apa ide terkini tentang masalah ini?

Saya menemukan makalah ini sangat menarik. Untuk meringkas: ini membahas mengapa dalam praktiknya Anda jarang menemukan contoh kasus terburuk dari masalah NP-lengkap. Gagasan dalam artikel ini adalah bahwa instance biasanya sangat di bawah atau sangat dibatasi, keduanya relatif mudah untuk diselesaikan. Itu kemudian mengusulkan untuk beberapa masalah ukuran 'kendala'. Masalah-masalah tersebut tampaknya memiliki 'transisi fase' dari 0 kemungkinan solusi ke kemungkinan 100%. Kemudian dihipotesiskan:

Bahwa semua masalah NP-lengkap (atau bahkan semua masalah NP) memiliki ukuran 'kendala'.
Bahwa untuk setiap masalah NP-complete, Anda dapat membuat grafik probabilitas solusi yang ada sebagai fungsi dari 'kendala'. Selain itu, grafik itu akan berisi fase-transisi di mana probabilitas itu dengan cepat dan dramatis meningkat.
Contoh kasus terburuk dari masalah NP-lengkap terletak pada fase-transisi.
Fakta apakah masalah terletak pada fase-transisi tetap tidak berubah di bawah transformasi dari satu masalah NP-lengkap ke yang lain.

Makalah ini diterbitkan pada tahun 1991. Pertanyaan saya adalah apakah ada penelitian lanjutan tentang ide-ide ini selama 25 tahun terakhir? Dan jika demikian, apa yang dipikirkan arus utama pada mereka? Apakah mereka ditemukan benar, salah, tidak relevan?

np-hardness worst-case dimpol
sumber

Contoh acak CSP, k-sat, k-pewarnaan telah dipelajari secara ekstensif oleh komunitas TCS. Sebagai contoh, fakta bahwa kepadatan / 'kendala' di mana kita dapat secara efisien menyelesaikan masalah tertentu seringkali lebih rendah daripada ambang batas di mana probabilitas solusi yang ada berjalan dari 1 ke 0 whp telah menarik banyak perhatian.

JWM

Berapa probabilitas ambang 'solvabilitas mudah' (secara kasar)? Apakah lebih seperti 0,2 atau lebih seperti 0,001?

dimpol

@impol biasanya tidak ada ambang batas yang tepat seperti yang didefinisikan. Intinya adalah pada apa "batasan" probabilitas pergi ke 0 atau 1 dengan ukuran input. Pernyataan tipikal adalah, "Algoritma A memecahkan instance 3-SAT acak dengan variabel dan klausa dengan probabilitas setidaknya , di mana pergi ke 1 dengan ." Ambang adalah nilai yang probabilitasnya berubah dari cenderung ke 0 ke cenderung ke 1.

n

$n$

Δ n

$\Delta n$

p_{n}

$p_n$

p_{n}

$p_n$

n

$n$

Δ

$\Delta$

Sasho Nikolov

pikir ide-ide telah sangat berpengaruh secara umum dan ada set makalah yang sangat besar terkait dengan topik ini dan penelitian terus berlanjut. Namun, ini merupakan konsep lintas sektoral karena transisi fase lebih banyak berasal dari fisika dan (lihat jawaban MATs di bawah) mungkin para ilmuwan komputer sedikit lebih skeptis tentang signifikansi mereka, dan juga tampaknya lebih mungkin konsep empiris / eksperimental. mungkin mencoba untuk menjawab di beberapa pt jika orang lain setuju dengan komentar ini, tetapi untuk saat ini mengundang / akan sangat mendorong diskusi / analisis lebih lanjut dalam Theoretical Computer Science Chat

vzn

lihat juga seberapa umum transisi fase dalam masalah lengkap NP . juga berpikir Walsh 1998 tepi pisau kendala adalah signifikan & belum ditindaklanjuti pada banyak, yang terkait dengan titik transisi tetapi mungkin tidak persis konsep yang sama ... kertas tidak menyebutkan fraktal secara langsung tetapi berpikir sangat sugestif dalam referensi untuk kemiripan diri, skala invarian, dll.

vzn

Jawaban:

Berikut adalah ringkasan kasar dari status berdasarkan presentasi yang diberikan oleh Vardi pada Lokakarya tentang Teori Model Hingga dan Algoritma (2012):

Diamati bahwa contoh-contoh sulit terletak pada fase transisi dari wilayah yang kurang terkendali. Dugaan mendasar adalah bahwa ada hubungan yang kuat antara fase-transisi dan kompleksitas komputasi masalah NP.

$P \ne NP$ $P$

Pemikiran arus utama saat ini tampaknya (sebagaimana dinyatakan oleh Vardi) bahwa transisi fase tidak secara intrinsik terhubung dengan kompleksitas komputasi.

Akhirnya, Ini adalah artikel yang dipublikasikan di Nature yang menyelidiki hubungan antara fase-transisi dan kekerasan komputasi K-SAT.

Mohammad Al-Turkistany
sumber

Terima kasih atas ulasannya, sangat disayangkan bahwa ini tidak mengarah pada terobosan nyata.

dimpol

Saya pikir fenomena menghancurkan dapat dianggap mengesampingkan kelas algoritma pencarian berbasis lokal yang merupakan dasar dari banyak algoritma heuristik untuk masalah NP-hard.

Kaveh

percakapan / video serupa / agak direvisi oleh Vardi, 2014, transisi fase & kompleksitas komputasi , stasiun penelitian internasional Banff

vzn

@vzn Nice, harus menonton video oleh Vardi.

Mohammad Al-Turkistany

Ya, ada banyak pekerjaan sejak koran Cheeseman, Kanefsky dan Taylor 1991.

Melakukan pencarian untuk tinjauan transisi fase dari masalah NP-Complete akan memberi Anda banyak hasil. Salah satu ulasan tersebut adalah Hartmann dan Weigt [1]. Untuk pengenalan tingkat yang lebih tinggi, lihat artikel Brian Hayes American Scientist [2] [3].

Makalah Cheesemen, Kanefsky dan Taylor 1991 adalah kasus yang disayangkan bahwa para ilmuwan komputer tidak memperhatikan literatur matematika. Dalam makalah Cheeseman, Kanefsky dan Taylor, mereka mengidentifikasi Siklus Hamilton sebagai memiliki fase transisi dengan pickup dalam biaya pencarian di dekat ambang kritis. Model grafik acak yang mereka gunakan adalah grafik acak Erdos-Renyi (probabilitas sisi tetap atau distribusi derajat Gaussian yang setara). Kasus ini telah dipelajari dengan baik sebelum makalah Cheeseman et all 1991 dengan algoritma waktu polinomial yang hampir pasti diketahui untuk kelas grafik ini, bahkan pada atau di dekat ambang kritis. "Grafik Acak" Bollobas adalah referensi yang baik. Bukti asli yang saya percaya disajikan oleh Angliun dan Valiant [5] dengan perbaikan lebih lanjut oleh Bollobas, Fenner dan Frieze [6]. Setelah Cheeseman,

Transisi fase untuk Siklus Hamiltonian dalam grafik acak Erdos-Renyi acak ada dalam arti bahwa ada transisi cepat probabilitas menemukan solusi tetapi ini tidak berarti peningkatan kompleksitas "intrinsik" untuk menemukan Siklus Hamiltonian. Hampir pasti ada algoritma waktu polinomial untuk menemukan Hamiltonian Cycles dalam Erdos-Renyi grafik acak, bahkan pada transisi kritis, baik dalam teori maupun dalam praktik.

Propagasi survei [8] telah berhasil dalam menemukan contoh yang memuaskan untuk acak 3-SAT sangat dekat dengan ambang kritis. Pengetahuan saya saat ini sedikit berkarat jadi saya tidak yakin apakah ada kemajuan besar dalam menemukan algoritma "efisien" untuk kasus yang tidak memuaskan di dekat ambang kritis. 3-SAT, sejauh yang saya tahu, adalah salah satu kasus di mana "mudah" untuk menyelesaikannya jika memuaskan dan mendekati ambang kritis tetapi tidak diketahui (atau sulit?) Dalam kasus tidak memuaskan dekat ambang kritis.

Pengetahuan saya agak ketinggalan jaman sekarang tetapi terakhir kali saya melihat subjek ini secara mendalam, ada beberapa hal yang menonjol bagi saya:

Hamiltonian Cycle "mudah" untuk grafik acak Erdos-Renyi. Di mana masalah sulitnya?
Nomor Partisi harus dipecahkan ketika sangat jauh di daerah probabilitas 0 atau 1 yang hampir pasti tetapi tidak ada algoritma yang efisien (setahu saya) ada untuk ukuran instance yang bahkan sedang (masing-masing 1000 nomor 500 bit, sejauh yang saya tahu, sepenuhnya tidak bisa digunakan dengan algoritma canggih). [9] [10]
3-SAT adalah "mudah" untuk instance yang memuaskan di dekat ambang kritis, bahkan untuk ukuran instance besar (jutaan variabel) tetapi sulit untuk contoh yang tidak memuaskan di dekat ambang kritis.

Saya ragu untuk memasukkannya di sini karena saya belum menerbitkan makalah peer-review darinya tetapi saya memang menulis tesis sayapada subjek. Gagasan utamanya adalah bahwa kemungkinan kelas ansambel acak (Hamiltonian Cycles, Number Partition Problem, dll.) Yang "secara intrinsik sulit" adalah yang memiliki properti "skala invarian". Distribusi Levy-stable adalah salah satu distribusi yang lebih alami dengan kualitas ini, memiliki kekuatan hukum ekor, dan orang dapat memilih contoh acak dari ansambel NP-Complete yang entah bagaimana menggabungkan distribusi Levy-stable. Saya memberikan beberapa bukti lemah bahwa instans Hamiltonian Cycle yang sulit secara intrinsik dapat ditemukan jika grafik acak dipilih dengan distribusi derajat Levy-stable daripada distribusi Normal (yaitu Erdos-Renyi). Jika tidak ada yang lain itu setidaknya akan memberi Anda titik awal untuk beberapa tinjauan literatur.

[1] AK Hartmann dan M. Weigt. Transisi Fase dalam Masalah Optimalisasi Kombinatorial: Dasar, Algoritma dan Mekanika Statistik. Wiley-VCH, 2005.

[2] B. Hayes. Masalah sulit termudah. American Scientist, 90 (2), 2002.

[3] B. Hayes. Di ambang pintu. American Scientist, 91 (1), 2003.

[4] B. Bollobás. Grafik Acak, Edisi Kedua. Cambridge University Press, New York, 2001.

[5] D. Angluin dan LG Valiant. Algoritma probabilistik cepat untuk sirkuit dan pencocokan Hamilton. J. Computer, Syst. Sci., 18: 155–193, 1979.

[6] B. Bollobás, TI Fenner, dan AM Frieze. Algoritma untuk menemukan jalur dan siklus Hamilton dalam grafik acak. Combinatorica, 7: 327–341, 1987.

[7] B. Vandegriend dan J. Culberson. Transisi fase G n, m tidaklah sulit untuk masalah siklus Hamilton. J. dari AI Research, 9: 219–245, 1998.

[8] A. Braunstein, M. Mézard, dan R. Zecchina. Perambatan survei: algoritme untuk kepuasan. Struktur dan Algoritma Acak, 27: 201–226, 2005.

[9] I. Gent dan T. Walsh. Analisis heuristik untuk partisi nomor. Kecerdasan Komputasi, 14: 430–451, 1998.

[10] CP Schnorr dan M. Euchner. Pengurangan basis kisi: Peningkatan algoritma praktis dan pemecahan masalah jumlah subset. Dalam Prosiding Dasar-Dasar Teori Komputasi '91, L. Budach, ed., Catatan Kuliah dalam Ilmu Komputer, volume 529, halaman 68-85, 1991.

pengguna834
sumber

25 tahun studi, dan di mana ide-ide saat ini:

+++ gagasan 1:

Dalam pengalaman saya pada penyelesaian yang memuaskan, saya telah menemukan dalam praktiknya bahwa menambahkan klausa k yang valid ke formula yang kita coba selesaikan sama dengan menentukan variabel (nk) qbf.

Itu tampaknya menjadi pendekatan untuk menunjukkan metode penyelesaian sat saat ini untuk NP adalah pspace-hard!

+++ gagasan 2:

Gagasan lain adalah bahwa masalah AllQBF adalah masalah nyata dalam hierarki boolean. Masalah AllQBFs adalah: Menghasilkan ekspresi boolean Q yang menentukan semua 2 ^ n qbfs dari rumus R. AllQBFs mudah ketika rumus asli R adalah monoton atau 2-cnf.

AllQBFs sepertinya jalan yang masuk akal untuk menunjukkan QBF adalah Exp, karena Q sering eksponensial, jadi mengevaluasi penugasan Q (kuantifikasi dari rumus R asli) adalah eksponensial. Jadi jalan untuk membuktikan NP adalah Exp setidaknya memiliki beberapa batu bata di dalamnya.

+++ ide 3: k-cnfs reguler

Btw, semua studi transisi fase telah melewatkan k-cnfs Reguler, di mana jumlah kemunculan variabel (di kedua arah) adalah tetap, mirip dengan grafik reguler derajat ... K-cnfs reguler menjadi jauh lebih sulit daripada model standar, karena semua variabel terlihat identik dalam hal kendala pada mereka.

Dua puluh lima tahun yang lalu, tepat setelah membaca cheeseman, saya memfokuskan pada derajat pewarnaan grafik biasa, karena semua variabel terlihat sama. Jadi saya akan menyalahgunakan hak jawaban saya di sini, dan menyajikan hasil lima puluh tahun pada grafik reguler!

+++ ide 4: Poin Emas untuk studi tolok ukur kepuasan

Saya telah mempelajari pewarnaan C grafik D vertex N reguler cukup luas. Tabel berikut merangkum hasil Golden Point untuk pewarnaan grafik biasa.

Untuk Probabilitas Tinggi, N instance acak memuaskan. Untuk Sangat Tinggi, N ^ 2 memuaskan. Untuk Super High, N ^ 3 instance acak cukup 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 ^ 2)) adalah:

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

Poin pewarnaan emas Super Probability (1 - 1 / (N ^ 3)) adalah:

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

Entri C4D9 menunjukkan empat pewarnaan grafik tingkat kesembilan. Ini adalah 4cnf acak terberat yang saya temui dalam 25 tahun penyelesaian sat. Saya baru-baru ini mewarnai grafik 172 titik sembilan titik setelah sepuluh hari waktu cpu.

+++ Idea 5: C5D16N ???? Golden Point agak dugaan ada.

Terima kasih, Daniel Pehoushek

daniel pehoushek
sumber

Ini bukan tempat yang tepat untuk menyajikan penelitian yang tidak dipublikasikan. Tulis makalah yang menjelaskan semuanya secara terperinci, letakkan di arxiv atau di tempat lain, dan poskan tautan di sini dengan ringkasan.

Sasho Nikolov

Titik pewarnaan grafik biasa C4D9 adalah titik sulit yang ekstrim, sesuai dengan judul dalam pertanyaan. Dibutuhkan sedikit konteks, sehingga sisa dari tabel.

daniel pehoushek