MAX-3SAT(13)

From Wikipedia, the free encyclopedia

MAX-3SAT(13) 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.

[edit] See also

[edit] References

  • 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
 This mathematical logic-related article is a stub. You can help Wikipedia by expanding it.