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:

  1. For some δ > 0, A uses at least 2nδ time.
  2. 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).