## MAX3SAT is Exponentially Hard to Approximate if NP Has Positive Dimension

John M. Hitchcock
**Abstract**:

Under the hypothesis that NP has positive
p-dimension, we prove that any approximation algorithm *A* for
MAX3SAT must satisfy at least one of the following:

- For some δ > 0,
*A* uses at least
2^{nδ} time.
- For all ε > 0,
*A*
has performance ratio less than 7/8+ε on an exponentially
dense set of satisfiable instances.

As a corollary, this solves one of Lutz and Mayordomo's "Twelve
Problems on Resource-Bounded Measure" (1999).