MAX-3LIN-EQN

MAX-3LIN-EQN

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 (2-δ) for any δ > 0.

ee also

*PCP (complexity)

References

*Rudich et al., "Computational Complexity Theory,"IAS/Park City Mathematics Series, 2004 page 108ISBN 0-8218-2872-X

*J. Hastad. "Some optimal inapproximability results."In proceedings of the 29th ACM STOC, 1-10, 1997


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • MAX-3SAT — is a problem in the computational complexity subfield of computer science. It generalises the Boolean satisfiability problem (SAT) which is a decision problem considered in complexity theory. It is defined as: Given a 3 CNF formula Φ (i.e. with… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”