MAX-3LIN-EQN

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

Эта проблема тесно связана с проблемой MAX-3SAT . NP -трудно аппроксимировать MAX-3LIN-EQN с соотношением (1/2 + δ) для любого δ > 0.

См. также

• ПЦП (сложность)

Ссылки

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

Серия IAS/Park City Mathematics, 2004 г., стр. 108 ISBN   0-8218-2872-X

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

В материалах 29-го ACM STOC, 1–10, 1997 г.