| 词条 | 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 (1/2 - δ) for any δ > 0. See also
References
IAS/Park City Mathematics Series, 2004 page 108 {{ISBN|0-8218-2872-X}}
In proceedings of the 29th ACM STOC, 1-10, 1997 1 : NP-hard problems |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。