is a problem in computational complexity theory
that is a restricted version of MAX-3SAT
. Every variable occurs in at most 13 clauses. MAX-3SAT(13)
is hard to approximate with approximation ratio 1 + δ for some δ > 0.
- Sanjeev Arora, "Probabilistic Checking of Proofs and Hardness of Approximation Problems," Revised version of a dissertation submitted at CS Division, U C Berkeley, in August 1994. CS-TR-476-94 http://www.cs.princeton.edu/~arora/pubs/thesis.pdf
- Rudich et al., "Computational Complexity Theory," IAS/Park City Mathematics Series, 2004 page 108 ISBN 0-8218-2872-X