Jump to content

MAX-3LIN-EQN

Add links
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Addbot (talk | contribs) at 03:16, 9 January 2013 (Bot: Removing Orphan Tag (Nolonger an Orphan) (Report Errors)). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

MAX-3LIN-EQN is a problem in Computational complexity theory where the input is a system of linear equations (modulo 2). Each equation contains at most 3 variables. The problem is to find an assignment to the variables that satisfies the maximum number of equations.

This problem is closely related to the MAX-3SAT problem. It is NP-hard to approximate MAX-3LIN-EQN with ratio (1/2 - δ) for any δ > 0.

See also

References

  • Rudich et al., "Computational Complexity Theory,"

IAS/Park City Mathematics Series, 2004 page 108 ISBN 0-8218-2872-X

  • J. Hastad. "Some optimal inapproximability results."

In proceedings of the 29th ACM STOC, 1-10, 1997

Retrieved from "https://en.wikipedia.org/w/index.php?title=MAX-3LIN-EQN&oldid=532102051"