Perambatan keyakinan untuk perkiraan 3LIN nyata?

22

Dalam sebuah makalah Science dari tahun 2002, Mezard, Parisi dan Zecchina mengemukakan heuristik propagasi kepercayaan untuk 3SAT acak. Eksperimen menunjukkan bahwa heuristik bekerja dengan baik untuk rasio kendala-per-variabel yang kemungkinan ada tugas yang memuaskan.

Pertanyaan saya adalah:

(1) Bagaimana jika Anda mempertimbangkan 3LIN acak dan bukan 3SAT acak? (setiap kendala adalah persamaan linear acak atas GF (2))

(2) Bagaimana jika Anda menganggap perkiraan acak 3LIN nyata? Apakah mungkin bahwa kinerja heuristik propagasi keyakinan (yang disesuaikan dengan tepat) akan lebih mudah untuk dianalisis dalam kasus ini?

c1x1+c2x2+c3x3=0c1,c2,c3x1,x2,x3|c1x1+c2x2+c3x3|ϵ

Intuisi adalah bahwa dalam versi perkiraan, perubahan keyakinan (apa yang seharusnya menjadi penugasan variabel) dapat terjadi secara kontinu / bertahap.

Dana Moshkovitz
sumber

Jawaban:

3

Dalam teori pengkodean, Belief Propagation banyak digunakan sebagai heuristik yang baik untuk mendekode (baik secara eksplisit atau secara acak) kode LDPC dalam berbagai pengaturan (misalnya, untuk saluran penghapusan, Anda ingin memenuhi semua kendala lebih cepat daripada eliminasi Gaussian. Untuk saluran bising , Anda ingin menemukan "paling cocok", dll). Saya pikir teknik yang digunakan ada yang relevan langsung dengan pertanyaan Anda. Anda mungkin ingin melihat buku "Teori Penyandian Modern" oleh Urbanke dan Richardson untuk diskusi yang luas.

KIA
sumber