В научной статье 2002 года Мезард, Паризи и Зекчина выдвинули эвристику распространения верований для случайного 3SAT. Эксперименты показывают, что эвристика хорошо работает для соотношений ограничений на переменную, для которых вероятно существует удовлетворительное назначение.
Мои вопросы:
(1) Что если вы рассмотрите случайный 3LIN вместо случайного 3SAT? (каждое ограничение является случайным линейным уравнением над GF (2))
(2) Что делать, если вы рассматриваете случайный приближенный реальный 3LIN? Можно ли предположить, что эффективность (надлежащим образом адаптированной) эвристики распространения убеждений было бы легче проанализировать в этом случае?
Примерная версия, определенная в недавней работе с Субхашом Хотом, выглядит следующим образом: переменные могут принимать реальные значения, а не только двоичные значения. Мы рассматриваем только присвоения нормы 1. Каждое уравнение имеет вид , где c 1 , c 2 , c 3 нормально распределены, а выбираются равномерно из набора переменных. Уравнение выполняется, если , а не только при точном равенстве.
Интуиция заключается в том, что в приблизительной версии изменения в убеждении (что должно быть присваиванием переменной) могут происходить непрерывно / постепенно.
источник