MAX-CUT: вероятностное округление/Задачи/2-boolean system — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) м (StasFomin переименовал страницу Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/2-boolean system в [[MAX-CUT: вероятностное округле…) |
StasFomin (обсуждение | вклад) (Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]]) |
(не показано 7 промежуточных версий этого же участника) | |
(нет различий)
|
Версия 15:49, 20 мая 2020
Максимальная совместная подсистема системы линейных булевых уравнений
Предложите 0.878-приближенный полиномиальный алгоритм для задачи о нахождении максимальной совместной подсистемы системы линейных булевых уравнений (сложения и умножения по модулю 2), для случая когда в каждое уравнение входит ровно 2 переменные. Будем считать, что правые части всех уравнений равны 1, т.е. все уравнения вида .
Стас Фомин 02:01, 15 июня 2011 (MSD): Ровно две переменных, но в каждом уравнении то они разные! Система уравнений из двух переменных это абсолютная банальщина