MAX-CUT: вероятностное округление/Задачи/2-boolean system — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 8: Строка 8:
 
{{remark|[[Участник:StasFomin|Стас Фомин]] 02:01, 15 июня 2011 (MSD): Ровно две переменных, но в каждом уравнении то они разные! Система уравнений из двух переменных это абсолютная банальщина}}
 
{{remark|[[Участник:StasFomin|Стас Фомин]] 02:01, 15 июня 2011 (MSD): Ровно две переменных, но в каждом уравнении то они разные! Система уравнений из двух переменных это абсолютная банальщина}}
  
[[Category:Решенные задачи]]
+
[[Category:Нерешенные задачи]]
 
<!--Вообще-то, решения уже есть-->
 
<!--Вообще-то, решения уже есть-->

Версия 07:49, 24 апреля 2014

Максимальная совместная подсистема системы линейных булевых уравнений

Предложите 0.878-приближенный полиномиальный алгоритм для задачи о нахождении максимальной совместной подсистемы системы линейных булевых уравнений (сложения и умножения по модулю 2), для случая когда в каждое уравнение входит ровно 2 переменные. Будем считать, что правые части всех уравнений равны 1, т.е. все уравнения вида .

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