Вера распространения для приблизительного реального 3LIN?

22

В научной статье 2002 года Мезард, Паризи и Зекчина выдвинули эвристику распространения верований для случайного 3SAT. Эксперименты показывают, что эвристика хорошо работает для соотношений ограничений на переменную, для которых вероятно существует удовлетворительное назначение.

Мои вопросы:

(1) Что если вы рассмотрите случайный 3LIN вместо случайного 3SAT? (каждое ограничение является случайным линейным уравнением над GF (2))

(2) Что делать, если вы рассматриваете случайный приближенный реальный 3LIN? Можно ли предположить, что эффективность (надлежащим образом адаптированной) эвристики распространения убеждений было бы легче проанализировать в этом случае?

Примерная версия, определенная в недавней работе с Субхашом Хотом, выглядит следующим образом: переменные могут принимать реальные значения, а не только двоичные значения. Мы рассматриваем только присвоения нормы 1. Каждое уравнение имеет вид , где c 1 , c 2 , c 3 нормально распределены, а выбираются равномерно из набора переменных. Уравнение выполняется, если , а не только при точном равенстве.с1Икс1+с2Икс2+с3Икс3знак равно0с1,с2,с3Икс1,Икс2,Икс3|с1Икс1+с2Икс2+с3Икс3|ε

Интуиция заключается в том, что в приблизительной версии изменения в убеждении (что должно быть присваиванием переменной) могут происходить непрерывно / постепенно.

Дана Мошковиц
источник

Ответы:

3

В теории кодирования распространение веры активно используется в качестве хорошей эвристики для декодирования (явных или случайно сгенерированных) кодов LDPC в различных настройках (например, для канала стирания, вы хотите удовлетворить все ограничения быстрее, чем устранение по Гауссу. Для шумных каналов. , вы хотите найти "наиболее подходящую" и т. д.). Я думаю, что методы, используемые там, имеют непосредственное отношение к вашему вопросу. Возможно, вы захотите взглянуть на книгу «Современная теория кодирования» Урбанке и Ричардсона для широкого обсуждения.

MCH
источник