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.

See also


  • 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
  • Rudich et al., "Computational Complexity Theory," IAS/Park City Mathematics Series, 2004 page 108 ISBN 0-8218-2872-X

Search another word or see MAX-3SAT(13)on Dictionary | Thesaurus |Spanish
Copyright © 2015, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature