Definitions

MAX-3SAT(13)

MAX-3SAT(13)

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

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

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

;