Просмотр исходного текста страницы MAX-CUT: вероятностное округление/Задачи/2-boolean system

== Максимальная совместная подсистема системы линейных булевых уравнений ==
Предложите <tt>0.878</tt>-приближенный полиномиальный алгоритм для задачи о
нахождении максимальной совместной подсистемы системы линейных булевых уравнений
(сложения и умножения по модулю 2), для случая когда в каждое уравнение входит ровно 2 переменные.
Будем считать, что правые части всех уравнений равны 1, т.е. все уравнения вида
<m>x_i+x_j=1 \ (\mod 2)</m>.

{{remark|[[Участник:StasFomin|Стас Фомин]] 02:01, 15 июня 2011 (MSD): Ровно две переменных, но в каждом уравнении то они разные! Система уравнений из двух переменных это абсолютная банальщина}}


<!--Вообще-то, решения уже есть-->

[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]