MAX-3LIN-EQN - MAX-3LIN-EQN

MAX-3LIN-EQN проблема в Теория вычислительной сложности где вход представляет собой систему линейных уравнений (по модулю 2). Каждое уравнение содержит не более 3 переменных. Проблема состоит в том, чтобы найти присвоение переменным, которое удовлетворяет максимальному количеству уравнений.

Эта проблема тесно связана с МАКС-3САТ проблема. это NP-жесткий приблизить MAX-3LIN-EQN с отношением (1/2 - δ) для любого δ> 0.

Смотрите также

• PCP (сложность)

Рекомендации

• Рудич и др., "Теория вычислительной сложности",

IAS / Park City Mathematics Series, 2004, стр. 108ISBN  0-8218-2872-X

• Дж. Хастад. «Некоторые оптимальные результаты о несовместимости».

В материалах 29-го заседания ACM STOC, 1-10, 1997 г.