Propagação de crenças para 3LIN real aproximado?

Em um artigo científico de 2002, Mezard, Parisi e Zecchina apresentaram a heurística de propagação de crenças para o 3SAT aleatório. As experiências indicam que a heurística funciona bem para proporções de restrições por variável para as quais é provável que exista uma atribuição satisfatória.

Minhas perguntas são:

(1) E se você considerar o 3LIN aleatório em vez do 3SAT aleatório? (cada restrição é uma equação linear aleatória sobre GF (2))

(2) E se você considerar o 3LIN real aproximado aleatório ? É concebível que o desempenho de uma heurística de propagação de crenças (adequadamente adaptada) seja mais fácil de analisar neste caso?

A versão aproximada, definida em um trabalho recente com Subhash Khot, é a seguinte: as variáveis ​​podem assumir valores reais e não apenas valores binários. Consideramos apenas atribuições da norma 1. Cada equação tem a forma , onde c 1 , c 2 , c 3 são normalmente distribuídos e x 1 , x 2 , x 3 são escolhidos uniformemente no conjunto de variáveis. Uma equação é satisfeita se $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$ , e não apenas se houver uma igualdade exata.$|c_1 x_1 + c_2 x_2 + c_3 x_3|\leq \epsilon$

A intuição é que, na versão aproximada, mudanças na crença (qual deve ser a atribuição de uma variável) podem ocorrer de maneira contínua / incremental.

Na teoria da codificação, a propagação de crenças é muito usada como uma boa heurística para decodificar (de forma explícita ou aleatória) códigos LDPC em várias configurações (por exemplo, para o canal de apagamento, você deseja satisfazer todas as restrições mais rapidamente do que a eliminação gaussiana. , você deseja encontrar o "melhor ajuste" etc.). Eu acho que as técnicas utilizadas são diretamente relevantes para sua pergunta. Você pode dar uma olhada no livro "Modern Coding Theory", de Urbanke e Richardson, para uma extensa discussão.