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?
Intuisi adalah bahwa dalam versi perkiraan, perubahan keyakinan (apa yang seharusnya menjadi penugasan variabel) dapat terjadi secara kontinu / bertahap.
sumber