Propagacja przekonań dla rzeczywistego przybliżenia 3LIN?

W artykule naukowym z 2002 r. Mezard, Parisi i Zecchina przedstawili heurystyczną propagację przekonań dla losowego 3SAT. Eksperymenty wskazują, że heurystyka działa dobrze dla współczynników ograniczeń na zmienną, dla których prawdopodobne jest istnienie zadowalającego przypisania.

Moje pytania to:

(1) Co się stanie, jeśli weźmiesz pod uwagę losowy 3LIN zamiast losowego 3SAT? (każde ograniczenie jest losowym równaniem liniowym nad GF (2))

(2) Co się stanie, jeśli weźmiesz pod uwagę losowe przybliżone rzeczywiste 3LIN? Czy można sobie wyobrazić, że wykonanie (odpowiednio dostosowanej) heurystycznej propagacji przekonań byłoby łatwiejsze do przeanalizowania w tym przypadku?

Przybliżona wersja, zdefiniowana w ostatniej pracy z Subhash Khot, jest następująca: zmienne mogą przyjmować wartości rzeczywiste, a nie tylko wartości binarne. Rozważamy tylko przypisania normy 1. Każde równanie ma postać , gdzie c 1 , c 2 , c 3 są zwykle rozłożone, a x 1 , x 2 , x 3 są wybierane równomiernie ze zbioru zmiennych. Równanie jest spełnione, jeśli $c_1 x_1 + c_2 x_2 + c_3 x_3 = 0$$c_1,c_2,c_3$$x_1,x_2,x_3$$|c_1 x_1 + c_2 x_2 + c_3 x_3|\leq \epsilon$

Intuicja jest taka, że ​​w przybliżonej wersji zmiany przekonań (jakie powinno być przypisanie zmiennej) mogą zachodzić w sposób ciągły / przyrostowy.

W teorii kodowania propagowanie przekonań jest szeroko stosowane jako dobra heurystyka do dekodowania (jawnych lub losowo generowanych) kodów LDPC w różnych ustawieniach (np. Dla kanału kasowania chcesz szybciej spełnić wszystkie ograniczenia niż eliminacja Gaussa. , chcesz znaleźć „najlepsze dopasowanie” itp.). Myślę, że zastosowane tam techniki są bezpośrednio związane z twoim pytaniem. Możesz rzucić okiem na książkę „Nowoczesna teoria kodowania” autorstwa Urbanke i Richardsona, aby przeprowadzić obszerną dyskusję.